2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 읽기 우선 문제 자체는 매우 짧고 예전에 싸피 수업 때 본 듯한 문제였다. 이런 문제는 직접!! 그려봐야 규칙이 보인다. 문제 풀기 우선 3xN의 크기의 판에 2x1, 1x2 크기의 타일을 남김없이 붙여 채워야 한다. 나는 규칙을 찾기 위해 N의 범위만큼 다 그려보았다. (N : 1~30) N = 0, 1 어차피 DP 배열은 0도 있을 거니까 그냥 그렸다 N이 0, 1일 때는 내가 가진 타일로 채울 수 없었다. N = 2 N = 2일 때는 위와 같은 방식으로 채울 수 있었다. 문제에서 주어진 답처럼 3가지 경우가 나왔다. N = 3 N = 3일 때를 그려보니 확실히 ..

2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 문제 읽기 예전에 동전 1 문제를 풀었었는데 DP 문제를 잘 못하다 보니 그때도 고생했었다. 결국 풀지 못하고 블로그 찾아봤던 기억이.. 이번에는 풀어보자! 하고 열심히 적으면서 했는데 예전 풀이가 기억나서 거기에 갇혀 좀 헤맸다. 기억이 아니라 논리에 의존해서 DP 문제를 풀고 싶구나.. 많이 풀다 보면 되겠지! 하는 생각이다. 문제 풀이 여러 차례 삽질했다. 바로 최종 문제 풀이로 넘어가도 상관 없을 듯 하다. 1차 삽질 : ..

9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 풀기 처음에 해당 문제를 봤을 때는 뭐지 했지만, 직접 그려보니 변의 길이가 어떻게 만들어지는지 규칙이 보였다. 그래서 다음과 같은 점화식을 만들어낼 수 있었다. 점화식 P[n] = P[n-1] + P[n-5] (n ≥ 5) P[0] = 0 P[k] = 1 (k = 1, 2, 3) P[k] = 2 (k = 4) 또한 문제에서 N의 범위가 1부터 100 사이 값이기 때문에 자료구조를 다음과 같이 크기 101인 배열로 정의하고, 미리 배열의 값을 채운 다음 입력 받..

9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 읽기 프로그래밍을 많이 해보지 않은 상황에서 처음으로 해당 문제를 보게 되면 모든 경우의 수를 세어 봐야 하나? 라는 생각이 들 수 있다. 하지만 입력의 크기인 N이 최대 10만이기 때문에 모든 경우를 세기에는 숫자가 너무 크다. 이럴 때 DP를 활용할 수 있다. 해당 문제는 DP의 기본적인 문제 중 하나이다. DP 문제는 DP 문제라는 것을 아는 것이 가장 어렵다고 한다. 어쩔 수 없이 많이 그려보며 많은 문제를 푸는 방법밖에 없는 것 같다. ..

문제 읽기 해당 문제는 가장 기본적인 0-1 Knapsack 문제이다. DP에 대한 이해를 위해 직접 표를 그려보자 예제 1 4 7 0: 6 13 (무게, 가치) 1: 4 8 2: 3 6 3: 5 12 물건개수/남은부피 1 2 3 4 5 6 7 0 0 0 0 0 0 13 13 1 0 0 0 8 8 13 13 2 0 0 6 8 8 13 14 3 0 0 6 8 12 13 14 둘 다 인덱스를 0부터 시작하면 남은 부피의 경우에는 비교를 하게 되기 때문에 인덱스 + 1을 한 상태가 실제 남은 부피가 되고, 이렇게 비교해줘야 한다. 따라서 그냥 k의 경우에는 1부터 k까지 설정하는 것이 좋다. 또한 N도 이전 컬럼을 보면서 비교하기 다음 컬럼을 채워나가기 떄문에 1부터 시작하는 것이 좋다. 즉, 점화식을 보고 ..

이 문제는 실버이긴 하지만 DP의 개념을 완전히 다지고 싶기 때문에 적어보기로 했다. 2579번: 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제읽기 이 문제는 dp문제 중 냅색 문제!!와 유사하다고 생각했다. 기존 냅색 문제의 경우, 개수 N, 부피 V의 두 개의 변수가 존재하고, 따라서 이차원 dp 배열을 사용한다. 그 다음 반복문을 이용하여 개수를 늘려가고, 해당 개수 안에서 부피를 늘려가며 최대 가치를 점화식을 이용해서 저장하게 된다. 현재 문제는 냅색 문제에서 좀 더 단순화(?) 된 버전인 것 ..