SY DevLog

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 각 사람이 돈을 인출하는데 필요한 시간을 최소로 하기 위해서는 돈을 인출하는데 걸리는 시간이 짧은 사람들부터 돈을 인출하면 된다. 각 사람에게 필요한 시간은 앞사람의 시간이 누적되어 더해진다. 그렇기 때문에 앞사람의 필요시간이 짧으면 짧을수록 누적된 시간이 짧기 때문에 총 합은 줄어들게 된다. 따라서 각 사람의 인출하는데 걸리는 시간을 오름차순으로 정렬한 후, 누적된 합을 더한다. 소스코드 :

www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 한 개의 강의실에 최대한 많은 회의를 넣기 위해서는 각 회의마다 끝나는 시간을 기준으로 오름차순 정렬을 해줘야 한다. 왜냐하면 앞에 회의가 일찍 끝날수록 뒤에 더 많은 회의가 회의실을 사용할 수 있기 때문이다. 먼저, 회의의 시작 정보와 끝나는 정보를 담은 Class 클래스를 생성하였다. 그리고 끝나는 시간이 짧은 순서대로 우선순위를 두어서 모든 Class를 우선순위 큐에 넣는다. 가장 먼저 큐에서 빠져나오는 회의는 모든 회의들 중 가장 일찍 끝나는 회의가 될 것이다. 예를 들어 문제 예제에서 (1, 4), (3, 5), (0..

11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 통나무를 선형으로 배열하는 것이 아니라 원형으로 배열하기 때문에 처음과 끝이 만난다. 그러므로 통나무를 단순히 오름차순, 혹은 내림차순으로 정렬하면 최소 난이도를 구할 수 없다. 예를 들어 오름차순으로 정렬하면 가장 왼쪽에는 최소값, 가장 오른쪽에는 최대값이 배치되는데, 원형이기 때문에 둘 사이의 차이도 난이도에 포함된다. 최대값에서 최소값을 뺀 값은 가장 큰 차가 되므로 최소 난이도를 구할 수 없다. 그래서 최소 난이도를 구하기 위해서는 중간에 위치한 통나무의..

2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net room 이차원 배열을 만들어서 방번호를 넣어준다. room 이차원 배열이 여기서 방문처리 역할을 한다. room[m][n] != 0 이미 방번호가 배정된 것이므로(방번호는 1번부터 시작하는 걸로 설정) 방문한 것이나 마찬가지가 된다. area 일차원 배열에는 해당 방들의 넓이를 넣어준다. ex) area[1] : 1번 방의 넓이, area[2] : 2번 방의 넓이 문제에서 성곽의 최대 넓이는 n=50, m=50 일 때 2500이고, 모든 공간마다 벽으로 ..