https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 난이도 : 실버 3 태그 : 다이나믹 프로그래밍 설명 다이나믹 프로그래밍에서 웰노운 문제들인 타일 시리즈. 이번엔 1과 00이라는, 조금 특이한 경우네요. 음... 어떻게 풀지 고민하다가, 결국 그냥 하나씩 써보면서 규칙성을 찾아보기로 했습니다. n = 2 11 00 2개 n = 3 100 001 111 3개 n = 4 0000 0011 1100 1001 1111 5개 n = 5 00001 00100 ..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 난이도 : 실버 1 태그 : 다이나믹 프로그래밍 설명 다이나믹 프로그래밍을 응용할 수 있겠는데요. XXXX7 라는 계단 수를 만들려면, 바로 직전 계단수는 뭘까요? 바로 XXX6, XXX8 입니다. 직전 값과 1만큼 차이가 나면 되는 것이죠. 즉, XXXX7이 될 수 있는 경우의 수는 XXX6의 경우의 수와 XXX8의 경우의 수를 더한 것과 같습니다. XXXX7는 5자리, 현재 값은 8 입니다. 이를 dp[자리 수(i)][값(j)] 으로 나타내면, dp[i][j] = dp[i-1][j-1] + dp[i-1][j..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 난이도 : 골드 5 태그 : 다이나믹 프로그래밍 설명 동전의 개수를 최소로 하는 문제입니다. 같은 단위의 동전이 여러개 주어질 수 있으므로 중복제거를 해야 합니다. dp의 각 원소는 각 동전을 만들기 위한 최소의 동전 개수입니다. 0원을 만들기 위한 동전의 개수는 0개이므로, dp[0] = 0으로 초기화합니다. 1, 5, 12원 동전을 사용해 15원을 만들어야 합니다..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 난이도 : 실버 2 태그 : 다이나믹 프로그래밍 문제 접근 이 문제는 처음 값부터 특정 값까지 가장 큰 부분을 찾는 문제가 아니라, 값이 최대가 되는 특정 구간을 찾는 문제입니다. 10 -4 3 1 5 6 -35 12 21 -1 예제에서는 12~21 부분이 되겠네요. 1 ~ 1 구간 : 10 1 ~ 2 구간 : 6 1 ~ 3 구간 : 9 1 ~ 4 구간 : 10 1 ~ 5 구간 : 15 1 ~ 6 구간 : ..
https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 난이도 : 브론즈 1 태그 : 수학, 다이나믹 프로그래밍 설명 피보나치 수는 재귀를 배울 때, 예시로 많이 쓰이지만, 다이나믹 프로그래밍(동적 계획법)의 예제로도 많이 쓰이죠. 이 문제 같은 경우는 재귀로는 풀 수 없으며, 다이나믹 프로그래밍(이하 dp)을 사용해 풀 수 있습니다. DP는 동적 계획법으로 번역할 수 있는데, 간단히 말하자면, 이전의 구한 값을 저..
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 난이도 : 실버 3 태그 : 다이나믹 프로그래밍 설명 자리수 n에 따라 각 값을 하나씩 구해보면 규칙성을 찾을 수 있습니다. n = 1 1 1개 n = 2 10 1개 n = 3 101 100 2개 n = 4 1000 1001 1010 3개 n = 5 10000 10001 10010 10100 10101 5개 n = 6 100000 100001 100010 100100 101000 101..
https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 난이도 : 실버 4 태그 : 다이나믹 프로그래밍 설명 규칙성을 찾아 풀이하는게 아닌, 그냥 이전에 구한 값을 사용해 다음 값을 구하는 문제입니다. 그냥 점화식을 그대로 소스코드로 옮기면 됩니다. 소스코드 fun main() { val br = Syst..
https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 난이도 : 실버 5 태그 : 다이나믹 프로그래밍 설명 규칙을 찾아 풀 수 있는 다이나믹 프로그래밍 문제입니다. 회차 문자열 A B 0 A 1 0 1 B 0 1 2 BA 1 1 3 BAB 1 2 4 BABBA 2 3 5 BABBABAB 3 5 회차가 오를 때마다, A는 이전 회차의 B, B는 이전 회차의 A + B의 값과 같습니다. 즉 A[i] = B[i-1] (i > 0, A[0] = 1) B[i] ..
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 난이도 : 골드 3 태그 : 다이나믹 프로그래밍, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 설명 DFS를 사용해 탐색하는 문제입니다. 다만, M, N이 500 이하의 자연수 이므로 DFS만 사용해서는 시간초과 / 메모리 초과가 발생하며, 다이나믹 프로그래밍 기법이 사용되어야 합니다 dp를 -1로 초기화하여 탐색을 하지 않는 공간을 나타냅니다. DFS를 이용해 탐색하며 이차원 배열 dp에 시작점에서 ..
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 난이도 : 골드 5 태그 : 다이나믹 프로그래밍, 슬라이딩 윈도우 설명 이전 값들을 이용하여, 최대값 및 최소값을 구하는 다이나믹 프로그래밍 문제입니다. 소스코드 전체 소스코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.StringTokenizer import kotlin.math.max import kotlin..