본문 바로가기

백준98

백준 10815번 : 숫자 카드 문제 www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 구현 방법 단순하게 이중포문으로 풀 수도 있지만 주어진 시간 제한은 2초, N과 M은 500,000이하 시간복잡도를 계산해보면 대충 O(NM) = 25억 정도로 시간 초과를 하기 때문에 저는 이분탐색으로 풀어주었습니다. 이분 탐색이란 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식으로 시간 복잡도가 훨씬 줄어들 수 있습니다. 간단하게 개념을 설명해보자면 수열이 있고 그 수열.. 2021. 3. 7.
백준 10026번 : 적록색약 문제 www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 구현 방법 둘다 bfs로 풀어주었고 적록색약이 아닌 사람일때와 적록색약인 사람일때와의 조건만 조금 다르게 해주었습니다. 처음에는 "같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다" 라는 말을 보고 적록색약이라는 말의 뜻을 제대로 생각하지 않고 두 글자를 두 개로 생각해서 적록색약인 사람은 두 가지의 색깔을 한 가지로 인식한다.. 라고 하고 풀었습니다. 당연히 틀렸습니다. 고.. 2021. 3. 7.
백준 2960번 : 에라토스테네스의 체 문제 www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 구현 방법 에라토스테네스의 체을 배경으로 구현하였고 문제 조건에 맞춰 조금씩 수정하였습니다. 이중포문을 돌려서 i가 2부터 N까지 내부 포문은 j는 i부터 N까지 i를 더해가며(배수) 반복해줬습니다. 해당 값이 이미 true라면 그냥 넘어가고 방문한 적이 없는 값이라면 방문처리를 해주고 카운트를 세주었습니다. 카운트가 K와 같으면 해당 값을 출력해주면 끝! 구현 코드 package BOJ.Silver.구현; import java.io.BufferedReader; import java.io.IO.. 2021. 3. 7.
백준 18310번 : 안테나 문제 www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 구현 방법 고민한거에 비해 너무나 간단했던.. 문제였습니다. 모든 집까지 거리의 총 합이 가장 최소가 되는 곳은 중간지점입니다. 중간지점보다 더 작은 값이 나올 순 없죠.. 그래서 입력된 집들의 위치를 정렬하여 가장 작은 값과 가장 큰 값의 중간 값을 구해주었습니다. 하지만 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우에는 가장 작은 값으로 출력 생각해보면 주어진 값이 홀수라면 중간값이 하나이지만 짝수라면 중간값이 두.. 2021. 3. 7.

티스토리툴바