[061] 15990. 1, 2, 3 더하기 5

✨ 알고리즘 분류 : 다이나믹 프로그래밍

 

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

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

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 1, 2, 3을 이용하여 합으로 나타내는 방법의 총 합을 계산

- 같은 수가 두번 이상 반복되면 안 됨

 

 

 

🧶 풀이과정 

 

1,2,3 더하기의 응용 버전이다

2024.04.12 - [Algorithm] - [058] 9095. 1,2,3 더하기

[058] 9095. 1,2,3 더하기

 

여기에서 문제는, 이 수들이 중복되지 않는 방법을 찾는 것에 있다.

처음에는 단순하게 2차원 배열로 생각하다가 아 이거 좀 너무 1차원적인데 하면서 다른 걸 노트에 써가면서 규칙을 찾았는데 당연히 그런 거 없었다 ^^ 내 두시간.

 

그럼 단순하게 푸는 걸 생각해보자

원래 이전에서는 현재 값에 대해서 구할 때 

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

 

의 형태로 구현했다.

여기에서 조금 더 생각해서, 중복이 없기 위해서는 끝자리가 무엇인지 알아야 한다.

적어도 내가 찾기에는 규칙을 찾기 어려웠고, 단순하게 각자를 따로 계산하는 것으로 들어갔다.

 

이제 nums[i][1] 에는 2와 3으로 끝나는 i-1 배열의 값

nums[i][2] 에는 1과 3으로 끝나는 i-2배열의 값

nums[i][3] 에는 1과 2로 끝나는 i-3배열의 값이 들어갈 것이다.

 

그러니까 자바 언어로 표현하면 다음과 같다.

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

 

 

 

 

🏹 제출코드

 

package data_structure_part_01;

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

public class Q15990 {

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

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

        long[][] dp = new long[100001][4];
        int n = Integer.parseInt(br.readLine());


        // 1 = 1+0
        // 2 = 2+0
        // 3 = 3+0 / 2+1 / 1+2

        dp[1][1] = 1;
        dp[2][2] = 1;
        dp[3][1] = 1;
        dp[3][2] = 1;
        dp[3][3] = 1;

        for(int i = 4; i <= 100000 ; i++){

            dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % 1000000009;
            dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % 1000000009;
            dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % 1000000009;

        }

        for(int i = 0 ; i < n ; i ++){
            int num = Integer.parseInt(br.readLine());
            System.out.println(dp[num][1] + dp[num][2] + dp[num][3]);
        }


        br.close();

    }
}