[JAVA-자바] 9095번: 1, 2, 3 더하기

 

1,2,3 숫자만을 사용해서 합으로 나타네는 방법의 수를 구하는 문제입니다.

 

1:
1
총 1가지

 

2:
1+1
2
총 (2가지)

 

3:
1+1+1
1+2
2+1
3
총 (4가지)

 

4:
1+1+1+1
1+1+2
1+2+1
1+3
2+1+1
2+2
3+1
총 (7가지)

 

5:
1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
1+1+3
1+2+2
1+3+1
2+1+1+1
2+2+1
2+1+2
3+1+1
3+2
총 13가지

 

이를 통해 N이 3이상이라고 가정했을 때, dp[N] = dp[N - 1] + dp[N - 2] + dp[N -3] 입니다. 소스코드로 옮겨보자면

 

소스코드:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] dp = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        // dp[4] = 7;
        for (int i = 4; i < 11; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        int cnt = Integer.parseInt(br.readLine());

        for (int i = 1; i <= cnt; i++) {
            int N = Integer.parseInt(br.readLine());
            bw.write(dp[N] + "\n");
        }

        bw.flush();
        bw.close();
    }
}

 

글의 내용 중 잘못된 점이나 수정이 필요한 부분, 혹은 궁금한 사항이 있다면 언제든 댓글로 남겨주시면 감사하겠습니다.

여러분의 피드백은 더 나은 글을 작성하는 데 큰 도움이 됩니다. 감사합니다.