[이론][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]

Leave a comment