백준 9095 - 1,2,3 더하기 [DP/JAVA]

https://www.acmicpc.net/problem/9095

 

---

사고방식

우선 쉬운 것부터. n이 1,2,3,4,5일때 정도를 직접 써보자.

1) n=1일 때, 경우의 수 : 1

-> 답:1

2) n=2일 때, 경우의 수: 1+1, 2

-> 답:2

3) n=3일 때, 경우의 수: 1+1+1, 1+2, 2+1, 3

-> 답:4

2) n=4일 때, 경우의 수: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2

-> 답:7

2) n=5일 때, 경우의 수: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2

-> 답:13

 

규칙이 혹시 보인다면 최고의 상황이다. 답은 "n번째 항은 n-1, n-2, n-3번째 항을 더한 값이다."이다. 

규칙이 안 보인다면 이렇게 접근해보자. (나도 이 쉬운 규칙을 못 찾아서 다음 방식으로 했다. 규칙이 한번에 눈에 들어오는게 마음 편하긴 하다.)

 

n=4일 때를 보자. 

1+1+1+1

1+1+2

1+2+1

2+1+1

1+3

3+1

2+2

 

현실적으로 생각해서 dp라는 것을 알고 있다고 가정하자. (아직 dp임을 모르는 상황에서 dp문제겠다 라고 판별할 능력이 부족하므로) 

그렇다면 어떻게든 메모이제이션을 써야하고 그러려면 n보다 전 항들을 써먹어야 한다. 

1,2,3의 합으로 n을 나타내는 것이기에 dp[4]는 dp[1+3], dp[2+2], dp[3+1].

즉, dp[1] 방법들에 3만 한번 더 더하는 것,

dp[2] 방법들에 2만 한번 더 더하는 것,

dp[3]방법들에 1만 한번 더 더하는 것과 같다.

 

예시를 들자면 

dp[1] = 1이며 방법은 '1'이다.

-> dp[4] = dp[1+3]이므로 dp[1]의 방법 '1'에 3만 한번 더해주면 된다. 즉, 

dp[4]는 '1+3'

 

dp[2] = 2이며 방법은 '1+1', '2'이다. 

-> dp[4] = dp[2+2]이므로 dp[2]의 방법 '1+1', '2' 에 2만 한번 더해주면 된다. 즉, 

dp[4]는 '1+1+2', '2+2'

 

dp[3] = 4이며 방법은 '1+1+1', '1+2', '2+1', '3' 이다.

-> dp[4] = dp[2+2]이므로 dp[3]의 방법 '1+1+1', '1+2', '2+1', '3' 에 1만 한번 더해주면 된다. 즉, 

dp[4]는 '1+1+1+1', '1+2+1', '2+1+1', '3+1'이다. 

 

따라서 dp[4]는 dp[1] + dp[2] + dp[3] = 7이 나온다. 

---

결론

점화식 : dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int [N+1];
        
        for(int i=0; i<N; i++){
            arr[i]=Integer.parseInt(br.readLine());
        }
        int dp[] = new int [11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for(int i=4;i<11;i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        for(int i=0; i<N; i++){
            System.out.println(dp[arr[i]]);
        }
    }
}