백준 9095번 - 1, 2, 3 더하기 [브루트 포스/자바 JAVA]

 

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

 

백준 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로 해보자라는 생각이 들기 시작해서 해보았더니 풀렸다.)  

그렇다면 어떻게든 메모이제이션을 써야하고 그러려면 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]]);
        }
    }
}