문제 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경�� www.acmicpc.net 문제 풀이 블루레이에 N개의 레슨이 들어가는데, 블루레이를 녹화할 때는 레슨의 순서가 바뀌면 안 되고 M개의 블루레이에 플레이 타임이 모두 같도록 해서 만들어야 한다. 이때 가능한 블루레이의 크기 중 최소를 출력하는 문제이다. 이 문제는 전형적인 이분 탐색 문제이다. start, end를 `max(lesson)`, `sum(lesson)`로 설정한다. 하나의 레슨을 담고자 한다면 최소 lesson에서 가장 큰 값은 되어야 한다. 하나의 블루레이에 모든 레슨을 ..
문제 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 풀이 문제에 F, S, G, U, D `(건물의 높이, 시작층, 가고자 하는 층, 한 번에 올라가는 층, 한 번에 내려가는 층)`가 주어진다. 시작 층에서 엘리베이터를 이용해 가고자 하는 층에 도달하는 최소 경우를 반환하는 문제이다. 만약 도달할 수 없다면 계단을 이용하라는 메시지를 출력한다. BFS를 통해 시작층 부터 올라가는 경우, 내려가는 경우를 탐색한다. 올라가는 경우 F보다 작거나 같아야 하며, 내려가는 경우는 0 보다 커야 한다. 재방문을 막기 위해 현..
1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 16195번: 1, 2, 3 더하기 9 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이하 이어야 한다. www.acmicpc.net 문제 풀이 앞서 다룬 1, 2, 3 더하기 7을 이해하고 있다면 쉽게 풀 수 있는 문제이다. 1, 2, 3 더하기 7에서는 N을 구할 때 M 만큼 사용 가능한 경우만 구하면 된다. 이 문제에서는 M이하의 모든 경우..
1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15993번: 1, 2, 3 더하기 8 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다. www.acmicpc.net 문제 풀이 앞의 문제들과는 다르게, 홀수인 경우와 짝수인 경우에 구할 수 있는 경우의 수를 나눠서 출력하여야 한다. 따라서 DP를 구성할 때, `DP[홀수/짝수][N]`과 같이 선언하여서 각 경우에 대해 점화식을 통해 찾아가면 ..
1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다. www.acmicpc.net 문제 풀이 N이라는 수를 1, 2, 3이라는 숫자를 사용하여 구할 때, M개의 숫자를 사용하여서 구할 수 있는 경우의 수를 찾는 문제이다. 문제를 풀기 위해서는 구하고자 하는 수 N과 사용하여야 하는 숫자 M이 있으므로..
1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15991번: 1, 2, 3 더하기 6 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 1, 2, 3의 합으로 N이라는 숫자를 나타내고자 할 때 수식이 대칭인 경우만 방법의 수로 취급하는 문제이다. 문제를 풀기 위해 N이 증가함에 따라 발생하는 경우의 수를 나열하면 아래와 같다. N은 1인 경우: 1개 `1` N은 2인 경우: 2개 `1 ..
1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 기존의 문제와 달리 연속된 숫자를 사용할 수 없다는 조건이 추가된 문제이다. 문제를 풀기 위해서 DP를 2차원 배열로 나누어 생각하면 쉽게 문제를 해결할 수 있다. 예를 들어 1, 2, 3 더하기의 경우 점화식을 `dp[n] = dp[n - 1] + d..
백준: 15989 1, 2, 3 더하기 4
1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 문제 풀이 기존의 1, 2, 3 더하기 문제와 다른 점이 있다면 순서가 다른 경우 하나의 경우로 생각한다는 것이다. 이를 구하기 위해서는 DFS로 조..
