[BOJ][JAVA] 15988: 1, 2, 3 더하기 3

 

 

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

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

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

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
    	int[] dp = new int[1000002];
    	dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;             //111 12 21 3

        for(int i=4; i<=1000001; i++) {
        	dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%1_000_000_009;
        }

        for(int t=0; t<tc;t++) {
        	int n = sc.nextInt();
            
            System.out.println(dp[n]);
        }
    }

 

 

---

오답노트(푸는 동안 사고과정 및 개선점)

기본 DP유형이라서 로직 구성하는 하는 건 어렵지 않았다. 

i번째 위치에서 경우의수가 이전 패턴에서 1,2,3의 경우가 추가되니까

i = i-1 + i-2 + i-3 인게 자연스럽다.

틀린이유는 범위 계산을 잘 못해서인데, 나머지로 10억 9를 처리하니까 당연히 될 줄 알았지만. 저 괄호로 묶인 것도 INT연산으로 돼서 INT가 연산할 수 있는 범위를 넘어가기 때문에 long으로 선언해서 해당 범위를 늘려줘야했다.

 

---

정답코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
    	long[] dp = new long[1000_002];
    	dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4; //111 12 21 3

        for(int i=4; i<=1000001; i++) {
        	dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%1_000_000_009;
        }

        for(int t=0; t<tc;t++) {
        	int n = sc.nextInt();
            
            System.out.println(dp[n]);
        }
    }
}

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^