[이론][DP] Chapter 0

dp입니다. 쉬운 문제부터 대표적인 유형을 보겠습니다.

---

최대 최소 문제

최대, 최소를 구하는 문제는 그리디 혹은 DP로 접근하면 풀리는 경우가 많습니다.

1로 만들기

1. 그리딜 접근해보면, 일단 나누기 3을 해보고 안되면 나누기 2를 해보고 안되면 1을 빼는 방법을 생각해봅니다. 하지만 이 경우는 10에서 2로 나누어 떨어지지만 9>3>1로 가는 것이 최소 방벙이기 때문에 그리디는 정해가 아닙니다.
2. 그래서 DP로 접근합니다.
3. queue를 사용해서 bfs 느낌으로 한 depth씩 진행하며 됩니다.
4. 아래와 같이 접근하면 1->2->4->5->10으로 접근해서 10입력 했을 때 4가 출력됩니다.
5. 1부터 *3 *2 +1을 해서 dp[i*3] = dp[i]+1과 같이 진행해줍니다.
6. 이미 값이 채워진 곳은 갱신하지 않습니다.

문제의 정답은 여기에서 확인할 수 있습니다.

1, 2, 3 더하기

문제의 정답은 여기에서 확인할 수 있습니다.

1. dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
2. i번째 숫자를 구성할 때 마지막 숫자가 1,2,3인 경우 각각의 경우의 수를 더하기
3. 4 = 3만들고 마지막에 +1 하는 경우의 수 + 2만들고 마지막에 +2하는 경우의 수 + 1만들고 마지막에 +3 하는 경우의 수
4. 위 gist의 댓글에 있는 풀이 방법 :recur(int curr, int sum)
5. curr : 현재 arr에 저장할 위치
6. sum : n이 채워질 때까지 남은 수
7. recur(curr+1, sum-i)를 통해서 arr가 [0,curr-1]까지 채워지자마자 가치치기 if문에 들어간다.
8. int형 return 값을 갖는 recur함수 풀이
9. 위 gist의 두 번째 댓글 참고

2*n 타일링

문제의 정답은 여기에서 확인할 수 있습니다.

1. 문제를 그려보면 피보나치 문제입니다. dp[i] = dp[i-1] + dp[i-2];

2*n 타일링2

문제의 정답은 여기에서 확인할 수 있습니다.

1. dp[i] = dp[i-1] + dp[i-2]*2;
2. 마지막이 1*2로 끝나는 경우 + 2 * 1 두 개로 끝나는 경우 + 2 * 2 1개로 끝나는 경우

이친수

문제의 정답은 여기에서 확인할 수 있습니다.

1. 2차원 dp 풀이
   • dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
   • dp[i][1] = dp[i - 1][0];
   • 출력 값 자료형 long long
2. 1차원 dp 풀이
   • n자리 이친수가 ??????라면, ?????0 또는 ?????1이다.
   • ?????0의 경우 ?????가 무엇이든 상관없이 때문에 dp[n-1]
   • ?????1의 경우 반드시 ????01이어야 하기 때문에 ????는 무엇이든 상관없으므로 dp[n-2]
   • 따라서 dp[i] = dp[i-1] + dp[i-2]