[백준] 1, 2, 3 더하기 - 자바

DP는 왜 이렇게 어려운지... 날 울린다...*

근데 식이 보이면 이렇게 허무할 수 없다.... 흥

 

1, 2, 3의 합은 각각

1 (1 가지)

1

2 (2 가지)

1 + 1

2

3 (4 가지)

1 + 1 + 1

1 + 2

2 + 1

3

 

 

4는 1, 2, 3씩 뺀 수와 표현할 수 있다.(1, 2, 3으로만 표현하기 위해)

즉, 3 + 1, 2 + 2, 1 + 3으로 표현할 수 있다.

3 (4 가지) + 1

1 + 1 + 1 + 1

1 + 2 + 1

2 + 1 + 1

3 + 1

2 (2 가지) + 2

1 + 1 + 2

2 + 2

1 (1 가지) + 3

1 + 3

 

 

즉 4를 표현하는 방식은

4 (4 + 2 + 1 = 7 가지)

1 + 1 + 1 + 1

1 + 2 + 1

2 + 1 + 1

3 + 1

1 + 1 + 2

2 + 2

1 + 3

 

4는 전부 1, 2, 3 끼리라 헷갈렸는데

5를 보면서 더 이해가 잘 됐음!

5는 1, 2, 3씩 뺀 수와 표현할 수 있다.(1, 2, 3으로만 표현하기 위해)

즉, 4 + 1, 3 + 2, 2 + 3으로 표현할 수 있다.

4 (7 가지) + 1

1 + 1 + 1 + 1 + 1

1 + 2 + 1 + 1

2 + 1 + 1 + 1

3 + 1 + 1

1 + 1 + 2 + 1

2 + 2 + 1

1 + 3 + 1

3 (4 가지) + 2

1 + 1 + 1 + 2

1 + 2 + 2

2 + 1 + 2

3 + 2

2 (2 가지) + 3

1 + 1 + 3

2 + 3

 

 

즉 5를 표현하는 방식은

5 (7 + 4 + 2 = 13 가지)

1 + 1 + 1 + 1 + 1

1 + 2 + 1 + 1

2 + 1 + 1 + 1

3 + 1 + 1

1 + 1 + 2 + 1

2 + 2 + 1

1 + 3 + 1

1 + 1 + 1 + 2

1 + 2 + 2

2 + 1 + 2

3 + 2

1 + 1 + 3

2 + 3

 

따라서 구해야 하는 숫자에 n 대해

n+1 만큼의 배열 dp를 만들어서 (0 ~ n 까지)

dp[1], dp[2], dp[3]에 각각 1, 2, 4를 대입한 후 

dp[4] 부터는 dp[n]까지 dp[j] = dp[j-1] + dp[j-2] + dp[j-3]를 만족하도록 for문을 돌려 대입해주었다.

for (int i = 0; i < N; i++) {
    int n = Integer.parseInt(br.readLine());
    int[] dp = new int[n+1];
    if (n >= 1) dp[1] = 1;
    if (n >= 2) dp[2] = 2;
    if (n >= 3) dp[3] = 4;
    for (int j = 4; j <= n; j++) {
        dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
    }

 

 

if (n >= 1) dp[1] = 1;
if (n >= 2) dp[2] = 2;
if (n >= 3) dp[3] = 4;

이 부분은 혹시라도 주어진 수가 3이하인 수가 있을까봐 if문을 붙여주었는데,

지금 if문을 없애고 돌려봤더니 런타임 에러 (ArrayIndexOutOfBounds)가 난다. (역시!)

 

아니면 문제에 "n은 양수이며 11보다 작다." 라는 조건이 있으니

int[] dp = new int[n+1] 대신 int[] dp = new int[11]를 대입해도 괜찮을 것 같다!

 

 

 

 

import java.io.*;
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());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] dp = new int[n+1];
            if (n >= 1) dp[1] = 1;
            if (n >= 2) dp[2] = 2;
            if (n >= 3) dp[3] = 4;
            for (int j = 4; j <= n; j++) {
                dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
            }
            sb.append(dp[n]).append("\n");
        }
        System.out.println(sb);
    }
}