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

---

```

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

```

이번 글을 통해 배워갈 내용

1. 백준 15990번 풀이

---

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

15990번: 1, 2, 3 더하기 5

 

 

백준 15990번 1, 2, 3 더하기 5는

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

 

정수 n 이 테스트 케이스만큼 주어지면

해당되는 정수를 두번이상 연속되지 않는 1, 2, 3의 합으로 나타내는 방법의  수를 구해주면 되는 문제입니다.

 

---

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

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

---

Dynammic Programming (동적 계획법)을 사용해서

앞에 수가 1이면 2 혹은 3

앞에 수가 2면 1 혹은 3

앞에 수가 3면 1 혹은 2

로 이전 경우의 수를 더해서 풀었습니다.

 

배열의 크기를 조금이라도 줄이고자 1씩 인덱스를 빼서

0은 1이고

1은 2

2는 3으로 인식해주시면 됩니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.IntStream;

public class Main {

    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringBuilder sb = new StringBuilder();

        long[] ans = findGivenPossibilities();

        final int testCase = Integer.parseInt(br.readLine());

        IntStream.range(0, testCase).forEach(k ->
        {
            try {
                sb.append(ans[Integer.parseInt(br.readLine())-1]).append("\n");
            } catch (IOException e) {
                e.printStackTrace();
            }
        });
        sb.setLength(sb.length() - 1);
        System.out.print(sb);
    }

    private static long[] findGivenPossibilities() {
        final int MAX_SIZE = 100001;
        final int MOD = 1000000009;
        long[] ans = new long[MAX_SIZE];

        long[][] arr = new long[MAX_SIZE][3];
        arr[0][0] = arr[1][1] = arr[2][0] = arr[2][1] = arr[2][2] = 1;
        ans[0] = ans[1] = 1;
        ans[2] = 3;

        for (int i = 3; i < MAX_SIZE; i++) {
            arr[i][0] = (arr[i - 1][1] + arr[i - 1][2]) % MOD;
            arr[i][1] = (arr[i - 2][0] + arr[i - 2][2]) % MOD;
            arr[i][2] = (arr[i - 3][0] + arr[i - 3][1]) % MOD;
            ans[i] = (arr[i][0] + arr[i][1] + arr[i][2]) % MOD;
        }
        return ans;
    }
}

//codemasterkimc.tistory.com [김씨의 코딩 스토리]

 

 

읽어주셔서 감사합니다

 

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

 

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

 

---