백준 15988번 1, 2, 3 더하기 3 JAVA 구현해보기

---

```

백준 15988번 1, 2, 3 더하기 3 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 15988번 풀이

---

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

15988번: 1, 2, 3 더하기 3

 

 

 

백준 15988번 1, 2, 3 더하기 3은

난이도 실버 등급의 문제로서

 

정수 n 이 주어질 때

1, 2, 3의 합으로 나타내는 방법의 경우에 수를 구하는 프로그램을 작성하면 됩니다.

 

예를 들어서

1 은 1 가지 (1)

2는 2 가지 (1+1, 2)

3 은 4 가지 (1+1+1, 1+2, 2+1, 3)

4는 7 가지로 표현이 가능하며

N 번째 숫자의 경우 값이 크기 때문에 문제에서는 모듈러 1,000,000,009로 연산 해준 값을 출력해주면 됩니다.

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

dp [i] = dp [i - 1] + dp [i - 2] + dp [i - 3]

 

i번째 숫자는 앞에 3개의 숫자의 경우의 수를 더한것과 같기 때문에

dp를 이용해서 풀어주면 됩니다.

 

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

public class Main {
    final static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


    public static void main(String[] args) throws IOException {

        // init
        final int kDpArrSize = 1000000;
        final int mod = 1000000009;
        long[] dp = new long[kDpArrSize + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        // dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        for (int i = 4; i <= kDpArrSize; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
        }

        StringBuilder sb = new StringBuilder();
        final int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            sb.append(dp[Integer.parseInt(br.readLine())]).append("\n");
        }
        sb.setLength(sb.length() - 1);
        System.out.println(sb);
    }
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

---