문제 13699번: 점화식다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1; t(n)=t(0)*t(n−1)+t(1)*t(n−2)+…+t(n−1)*t(0). 입력으로 0 ≤ n ≤ 35가 주어질 때 t(n)을 출력하는 문제이다.www.acmicpc.net 풀이 주어진 점화식을 그대로 따라가면 쉽게 해결할 수 있으며 DP를 이용해 카탈란 수(Catalan Number)를 구할 수 있다. 카탈란 수는 조합론에서 사용되는 특정한 구조를 만들 수 있는 경우의 수를 나타낸다. 수열 C₀, C₁, C₂, … 을 카탈란 수라고 하며, 첫 몇 개는 다음과 같다:C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, …카탈란 수 Cₙ은 다음 점화식으로 정의된다.$..

문제 10211번: Maximum Subarray크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 문제이다.www.acmicpc.net 풀이 연속된 부분 수열의 합 중 최댓값을 구하는 전형적인 DP(Dynamic Programming) 문제이다. 입력받은 현재 값을 더해가며 최대 부분합을 갱신한다. 이때, 합이 음수라면 새로운 구간을 시작하면 된다. 코드 fun main() { val sb = StringBuilder() repeat(readln().toInt()) { val num = readln().toInt() val arr = readln().split(' ').map { it.toI..

문제 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net 풀이 문제에서 1, 1, 2, 3, 5, ... 을 보면 알 수 있듯이 정사각형 타일의 한 변의 길이는 피보나치 수열로 증가한다. 따라서 반복문을 이용하여 DP 계산을 해주면 타일의 길이를 계산할 수 있다. N개의 타일로 구성된 전체 타일은 한 변의 길이가 dp[N]이고, 다른 변의 길이는 dp[N] + dp[N-1], 즉 dp[N + 1] 이 된다. 그렇기 때문에 전체 타일의 둘레는 dp[N]*2 + dp[N+1]*2 로 구하면 된다. 코드 fun main(..

문제 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP(동적 프로그래밍)으로 해결하는 문제이다. 민규가 카드를 N개를 구매하는 방법은 여러가지가 있으며 다음과 같다. - 카드 1개가 포함된 카드팩 + 카드 N-1개 구매: price[1] + dp[N-1] - 카드 2개가 포함된 카드팩 + 카드 N-2개 구매: price[2] + dp[N-2] - 카드 3개가 포함된 카드팩 + 카드 N-3개 구매: price[3] + dp[N-3] ... - 카드 M개가 포함된 카드팩 + 카드 N-M개 구매(점화식): $d..

문제 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP(동적 프로그래밍)으로 해결하는 문제이다. 민규가 카드를 N개를 구매하는 방법은 여러가지가 있으며 다음과 같다. - 카드 1개가 포함된 카드팩 + 카드 N-1개 구매: price[1] + dp[N-1] - 카드 2개가 포함된 카드팩 + 카드 N-2개 구매: price[2] + dp[N-2] - 카드 3개가 포함된 카드팩 + 카드 N-3개 구매: price[3] + dp[N-3] ... - 카드 M개가 포함된 카드팩 + 카드 N-M개 구매(점화식): $dp[..