1, 2, 3 더하기 시리즈

1, 2, 3 더하기 시리즈는 DP 문제의 감을 잡기 좋은 것 같다.

푸는 문제마다 업데이트 할 예정이고, 푼 문제들을 정리할 겸 어떻게 접근하는지 간략하게 적어본다.

각 문제마다 Top Down, Bottom up 두 가지 방식으로 풀어보는걸 추천한다.

1, 2, 3 더하기

n의 크기가 작기 때문에 메모이제이션을 쓰지 않아도 풀리는 문제이다.

1, 2, 3 더하기 3

접근 : 

n의 크기가 10^6이기 때문에 모든 경우를 다 계산하면 시간초과가 발생한다.

잘 생각해보면, 답을 구하는데 부분 문제가 겹치는걸 알 수 있다.

 

풀이 : 

점화식을 세워보면 다음과 같다.

dp[N] = dp[N - 1] + dp[N - 2] + dp[N - 3]

1, 2, 3 더하기 4

접근 : 

순서와는 상관 없이 사용된 수의 개수가 같으면, 같은 경우로 치는 조건이 추가되었다.

그렇다면 중복을 어떻게 제거할 수 있을까

예시를 보면서 테이블을 설계해보자

4를 만들어야 하는 경우

1 + 1 + 1 + 1

1 + 1 + 2

2 + 2

1 + 3

보통 순서와 상관 없이 판단하기 위해서 먼저 만들어지는 경우를 기준점으로 삼는데, 이 문제에선 오름차순으로 기준을 삼는다.

오름차임을 판단하기 위해서는 이전에 사용했던 숫자가 무엇인지 알아야 한다. 그런데, 1차원 테이블로는 기록할 수 없다. 따라서, 2차원 테이블로 차원을 늘려 이전에 사용한 숫자를 기록한다.

즉, 점화식을 세우면 다음과 같다.

dp[N][1] = dp[N - 1][1]

dp[N][2] = dp[N - 2][1] + dp[N - 2][2] //2를 사용하면서, 마지막 숫자가 1, 2인 경우

dp[N][3] = dp[N - 3][1] + dp[N - 3][2] + dp[N - 3][3] //3을 사용하면서 마지막 숫자가 1,2,3인경우

1, 2, 3 더하기 5

접근 : 

같은 수를 연속해서 사용할 수 없는 조건이 걸렸다.

연속임을 판단하기 위해선 이전에 사용했던 숫자가 무엇인지를 알아야 한다. 그런데, 1차원 테이블로는 이전에 사용했던 숫자를 알 수 없기 때문에 차원을 늘리는 접근을 해야 한다.

즉, 테이블에 기록되는 정보는 N을 만드는 경우의 수 + 마지막으로 사용한 숫자가 동시에 기록이 되어야 한다.

 

풀이 : 

점화식을 세워보면 다음과 같다.

dp[N][1] -> 마지막 숫자로 1을 사용하여 N을 만드는 방법의 수

dp[N][1] = dp[N - 1][2] + dp[N - 1][3]

dp[N][2] = dp[N - 2][1] + dp[N - 2][3]

dp[N][3] = dp[N - 3][1] + dp[N - 3][2]

Answer = dp[N][1] + dp[N][2] + dp[N][3]