BOJ15990

Baekjoon 15988 : 1,2,3 더하기 5

논리순서

1. dp[n] 에는 n 을 1,2,3 을 사용해 만들수 있는 방법의 수가 들어간다.
2. dp[1],dp[2],dp[3] 까지는 규칙이 적용 되지 않기 때문에 값을 직접 넣어준다.
3. dp[n]을 계산 할때 원래 방법의 수는 dp[n-1] + dp[n-2] + dp[n-3]이지만 이 문제에선 연속된 수가 올수 없다.
4. 따라서 dp[n]을 맨 앞에 1, 2, 3이 올때를 나누어 이전 값의 1로 시작하는 값을 빼고 2, 와 3 , 2로 시작하는 값을 빼고 1과 3 , 3으로 시작하는 값을 빼고 1과 2 를 각각 더해준다.
   • 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-2][2]

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