문제 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[..

문제 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이 이 문제는 최장 증가 수열(LIS, Longest Increasing Subsequence)을 구하는 문제로, 동적 프로그래밍(DP)을 활용하여 해결할 수 있다. 입력받은 배열에서 반복문을 통해 현재 위치에서 앞의 원소들의 값과 비교하며 값을 갱신하면 된다. 만약 앞의 원소가 현재 원소보다 작다면 상자에 넣을 수 있으므로 해당 위치의 값 + 1을 현재 위치의 DP값과 비교하여 갱신해주면 된다. [1, 6, 1, 7, 5, 8]에 대해 LIS을 구하는 알고리즘을..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP를 활용하여 해결할 수 있으며 주어진 예제 입력을 dp 배열로 메모이제이션한다면 다음과 같다. arr 10 20 10 30 20 50 dp 1 2 1 3 2 4 10은 10보다 작은 값이 없기 때문에 길이가 1인 수열이 되고, 50은 10, 20, 30, 50으로 길이가 4인 수열이 된다. 이를 DP로 해결하기 위한 반복문을 만들어보자. 입력 받은 배열을 순회하며 각 원소..