SY DevLog

8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 이 문제는 이분탐색을 이용하여 해결할 수 있다. 사대의 위치를 arr 배열에 오름차순으로 정렬한다. 정렬 전 : 6 1 4 9 정렬 후 : 1 4 6 9 특정 동물의 위치에서 가장 가까운 사대의 위치를 이분탐색으로 찾는다. 이분탐색을 진행하는 방법은 다음과 같다. arr[middle] == x 이분탐색 범위(left ~ right)에서 arr[middle]가 동물의 x좌표와 일치한다면, 즉 사대가 같은 세로 일직선 상에 존재한다면 이 때의 사대가 동물과의 거리가..

2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net R : 홀수 OR C : 홀수 R, C 둘 중에 하나라도 홀수이면 모든 칸에 있는 기쁨을 다 더할 수 있다. 모든 칸을 다 방문할 수 있다. R : 짝수 AND C : 짝수 문제는 R과 C 둘 다 짝수인 경우이다. R과 C 둘 다 짝수인 경우에는 모든 칸을 다 지날 수 없기 때문에 기쁨의 합이 최대가 되는 방법을 생각해야한다. 처음에는 dfs를 이용하여서 모든 가능한 경로를 다 탐색한 후에 기쁨의 합이 최대가 되는 경로를 출력하도록 했었다. 그러나 결과는 '..

1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net A[r][c]에 대하여 A[r][c]!=B[r][c] 이면, (r, c)를 시작으로하는 3*3 행렬만큼 0은 1로, 1은 0으로 뒤집는다. 위 과정을 r = 0, c = 0 부터 마지막까지 반복한다. 이렇게 하는 이유는 만약에 A[0][0]!=B[0][0] 라면 B[0][0]와 같게 하기 위해 A[0][0]를 뒤집어야 한다. 그런데 A[0][0]를 뒤집기 위해서는 결국 (0,0)을 맨 왼쪽위로 하는 3*3 행렬만큼을 뒤집어야 한다. A[0][1]도 마찬가지이다. A[0][1]..

1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 어려워서 오래 걸렸던 문제.. 다른 풀이를 참고해서 문제를 해결하였다. 해결 방법은 다음과 같다. 1. 1부터 N까지를 오름차순으로 정렬한다. (ex. N = 13, M = 5, K = 4) 2. 수열을 M묶음으로 나눈다. 이때 하나의 묶음에는 숫자가 K개 혹은 그 이하가 들어있어야 한다. 또한, 적어도 하나의 묶음은 K개의 수가 존재해야 한다. 3. M개의 묶음으로 나누었으면 각각의 묶음 내의 수들을 내림차순으로 정렬한다. M묶음으로 나누는 이유는 각각의 묶음에서 숫자 하나씩 선택을 하면 M개의 증가하는 수열을 만들 수 있다. 아래 그림에서 묶음1에서는 4를, 묶음2에서는 7, 묶음3에서는 8, 묶음4에서는 ..

1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 막상 문제를 풀고 나니 허무할 정도로 간단한데, 규칙을 찾는데까지 너무 오랜 시간이 걸렸다.. 이 문제는 케이스를 나누어서 각 케이스 별로 방문한 칸을 구하는 것이 중요하다. 먼저, 나이트가 이동할 수 있는 위치는 다음과 같다. 문제에서 조건이 주어지는데, 4번 이상 움직일 때는 4가지 방법으로 모두 움직여야 하지만, 3번까지 움직일 때는 4가지 방법을 모두 사용하여 움직일 필요가 없다는 점이다. 3번 이동할 때까지는 똑같은 방법으로만 움질이는 것도 가능하다. 나이트가 아예 움직일수 없는 경우 ( N = 1 || M = 1 )..

1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 정육면체를 이루는 주사위를 3면이 다 보이는 경우, 2면만 보이는 경우, 1면만 보이는 경우 이렇게 3가지로 나눌 수 있다. 그리고 각각에 해당하는 주사위의 개수를 N에 대한 식으로 나타내면 다음과 같다. 3면만 보이는 주사위의 개수 : 4 2면만 보이는 주사위의 개수 : 8(N-2) + 4 1면만 보이는 주사위의 개수 : 5(N-2)^2 + 4(N-2) 3면이 보이는 주사위 3면이 보이는 주사위에서 최소값은 한 모서리를 공유하는 주사위의..

9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net b를 기준으로 오름차순으로 정렬하고, b가 같을 때는 a를 기준으로 내림차순으로 정렬한다. 나는 우선순위 큐를 사용하여 b가 작을수록 우선순위가 높고, b가 같으면 a가 클수록 우선순위가 높도록 설정한 뒤, 우선순위 큐에서 범위 (a,b)를 하나씩 꺼내었다. PriorityQueue pq = new PriorityQueue(M, (Range r1, Range r2) -> (r1.b == r2.b) ? r2.a - r1.a : r1.b - r2.b); book 일차원..

1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 자체는 쉬워보였는데 생각하지도 못한 반례가 몇 개 있어서 시행착오를 겪었다. 우선, 양수만 놓고 보면 최대값이 나오기 위해서는 내림차순으로 정렬해서 큰수끼리 차례대로 곱해주면 된다고 생각했다. ex) 5 4 3 2 1 일 경우, (5*4) + (3*2) + 1 = 27 만약에 음수가 존재한다면 음수는 절대 양수와 곱해져서는 안된다. 음수 x 양수는 더 작은 음수가 되기 때문이다. 그래서 음수는 같은 음수와 곱해지거나 혹은, 0과 곱해져서 음수를 상쇄시켜야..

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 입력받은 수식의 결과가 최소가 되기 위해서는 먼저 모든 더하기 연산을 한 후, 빼기 연산을 해주면 된다. 우선 입력받은 문자열을 '-'을 기준으로 나눠서 문자열 배열에 담는다. 입력받은 문자열이 55-50+40 이면 "55" 와 "50+40" 로 나누어진다. arr[0] = "55", arr[1] = "50+40" 나누어진 문자열에 '+'가 포함되어 있으면 더하기 연산을 진행한 후 결과값으로 대체한다. 먼저 "55"에는 '+' 문자가 없기 때문에 아무런 처..

11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 각 사람이 돈을 인출하는데 필요한 시간을 최소로 하기 위해서는 돈을 인출하는데 걸리는 시간이 짧은 사람들부터 돈을 인출하면 된다. 각 사람에게 필요한 시간은 앞사람의 시간이 누적되어 더해진다. 그렇기 때문에 앞사람의 필요시간이 짧으면 짧을수록 누적된 시간이 짧기 때문에 총 합은 줄어들게 된다. 따라서 각 사람의 인출하는데 걸리는 시간을 오름차순으로 정렬한 후, 누적된 합을 더한다. 소스코드 :