[알고리즘] - 백준 15988번 : 1,2,3 더하기 3 (JAVA)

🎯 문제

문제의 출처 : 백준 15988번

🚀 풀이 방법

문제를 먼저 봅시다!
문제는 주어진 정수를 1,2,3의 합으로 나타내어지는 방법의 수를 구하는 것입니다.

문제의 예시를 보시면 4를 1,2,3의 합으로 나타내는 것을 보실 수 있습니다.
1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 2+1+1
5. 2+2
6. 1+3
7. 3+1
로 총 7가지이며

1,2,3의 수는 같은데 순서가 달라도 다른 경우의 수로 인정된다는 것을 헷갈리면 안됩니다!

ex) 1+1+2 와 1+2+1, 2+1+1은 서로 서로 하나의 경우로 인정

점화식을 한번 도출해 내 봅시다!
4를 1,2,3의 합으로 어떻게 나타낼 수 있는지 보죠

검정 글씨는 나타낼 수있는 경우를 의미하며 빨간 글씨는 주어진 정수를 도출하기 위해 더해야하는 수(1,2,3 중 하나)를 의미 합니다.

• 1을 나타낼 수 있는 경우에서 4를 만드는 법
  1. 1+3
• 2를 나타낼 수 있는 경우에서 4를 만드는 법
  2. 1+1+2
  3. 2+2
• 3을 나타낼 수 있는 경우에서 4를 만드는 법
  4. 1+2+1
  5. 2+1+1
  6. 1+1+2
  7. 3+1

[점화식]

dp[1]=1
dp[2]=2
dp[3]=4

dp[n]=dp[n-1]+dp[n-2]+dpn-3이 도출 되며 문제 조건을 보시면 출력을 1,000,000,009로 나눈 나머지를 하라 하였으므로

👏 최종적으로
(n>=4)
dp[n]=(dp[n-1]+dp[n-2]+dp[n-3])%1,000,000,009

🚀 CODE

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception{
        
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int t=Integer.parseInt(st.nextToken());
        long[] dp=new long[1000001];
        List<Long> res=new ArrayList<>();

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

        for(int i=1;i<=t;i++){
            st=new StringTokenizer(br.readLine());
            int temp=Integer.parseInt(st.nextToken());
            
            for(int j=4;j<=temp;j++){
                if(dp[j]==0)
                    dp[j]=(dp[j-2]+dp[j-1]+dp[j-3])%1000000009;
            }
            res.add(dp[temp]%1000000009);
        }

        for (Long result : res) {
            System.out.println(result);
        }
    }
}

이상으로 포스팅을 마치겠습니다. 감사합니다 :) 👋