문제

1,2,3 더하기 4

풀이

이 문제는 이전에 풀었던 문제의 응용문제 인데 흔한 dfs 으로 풀면 시간초과 가 난다. 이문제는 점화식을 세워야 하는 문제인데 이전에 백준 강의들을때 기본 문제로 있었는데 전혀 생각이 안났다... 이럴수가 멍청이인듯

구해야 하는 값이 d[i] 라고 치면 해당 점화식은 다음과 같다

d[i] = d[n-1]+dp[n-2]+dp[n-3]

dp[1] 은 1로 i를 만들 수 있을 때 사용하는 개수
dp[2] 는 2로 i를 만들 수 있을 때 사용하는 개수
dp[3] 는 3로 i를 만들 수 있을 때 사용하는 개수
이런 식으로 점화식을 전부 다 더하면 되는 것인데

i = 3 일때
1을 세번 쓰는 방법
2를 한번 쓰고 1을 한번 쓰는 방법
3을 한번 쓰는 방법이 있다
해당 내용을 점화식으로 작성하면 아래와 같다

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

일단 해당 문제를 dp로 파악하는 능력이 안되는 것 같다.
이전에 1,2,3 더하기문제는 dfs로도 간단히 풀렸는데 그 이유가 11까지로 n의 값이 상당히 작았기 때문이었다..ㅠ
꼭 dfs 로 풀어야 한다는 강박 같은게 있는건지..... 조금만 더 복잡도를 생각했더라면..

풀이는 토니님 풀이를 참고했다

		for (int i = 4; i <= n; i++) {
            for (int j = 1; j <= 3; j++) {
                int sum = 0;
                if (j == 1) {
                    dp[i][j] = 1;
                    continue;
                } else {
                    for (int k = 1; k <= j; k++) {
                        sum += dp[i - j][k];
                    }
                    dp[i][j] = sum;
                }
            }
        }

나중에 꼭 다시 풀어봐야 할 문제이다

전체 코드

전체 코드