9095: 1, 2, 3 더하기

[minsoo0715]

9095: 1, 2, 3 더하기

소스 코드

아이디어

1을 먼저 고르는 경우, 2를 먼저 고르는 경우, 3을 먼저 고르는 경우를 생각해보면

• 1을 먼저 고르는 경우의 수 = n-1을 만드는 경우의 수
• 2를 먼저 고르는 경우의 수 = n-2를 만드는 경우의 수
• 3을 먼저 고르는 경우의 수 = n-3을 만드는 경우의 수

세 가지 경우를 생각해볼 수 있다.
일단 1, 2, 3에 대해서 생각해보자
1은 1의 한 가지 경우
2는 1+1, 2의 두 가지 경우
3은 1+1+1, 1+2, 2+1, 3의 세가지 경우가 존재한다.

이제 4를 생각해보자

• 1을 먼저 고르는 경우 = 3을 만드는 경우의 수 = 3가지
• 2를 먼저 고르는 경우 = 2를 만드는 경우의 수 = 2가지
• 3을 먼저 고르는 경우 = 1을 만드는 경우의 수 = 1가지
  각각의 경우를 다 더해주면 7가지임을 알 수 있다.

따라서 점화식은 다음과 같음을 알 수 있다.
$$A_n = A_{n-1} + A_{n-2} + A_{n-3} \quad (n\geq4)$$

구현

입력을 여러 개 받기 때문에 재귀로 top-down 방식으로 구현 했다.

int solve(int k) {
    if(dp[k] != 0) // 값을 한번 구한 경우
       return dp[k];
    return dp[k] = solve(k-1) + solve(k-2) + solve(k-3);
}