[백준] 1, 2, 3 더하기 5 - 자바

1. 문제

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

 

2. 접근

문제가 너무 DP스러워서 바로 경우의 수들을 차례차례 써봤다. 처음에는 잘 안보였는데 연속해서 사용하면 안된다 조건에 집중해서 계속 생각해봤다. 1이 마지막에 나오면 그 후엔 2와 3만 올 수 있고 그러면 n-2와 n-3에서 정보를 가져와야 할텐데.. 또 마지막에 나오는 수를 저장하기 위해 2차원 배열을 사용해볼까! 하다가 점화식이 떠올랐다

 

나온 점화식은 아래와 같다

dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % MOD
dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % MOD
dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % MOD
-> result : dp[i][1] + dp[i][2] + dp[i][3]

 

 

3. 몇가지 실수

점화식을 세우고 문제를 풀었는데 시간초과가 나왔다. 그래서 탑 다운 방식으로 재귀적으로 풀어보기도 하였는데 마찬가지로 시간초과가 나왔다. 이유는 테케마다 DP 배열을 계속 새롭게 구해줘서였다. 또한 long 타입으로 지정했어야 했는데 int로 result 값을 저장해서 오답이 나왔다. 이젠 그냥 싹다 long으로 할까...하다가도 백준 아니면 안먹힐 것 같아서 다음부터는 범위에 주의해서 적절한 타입을 선택하는 것에 ㅣ집중해야겠다.

 

아무튼 정리하자면 

• 여러 개의 테케를 구해야 되는 문제는 최초 한 번 Max값까지 계산을 해둬서 재활용 하는 것이 시간 절약 (Max값 주의)
• DP는 왠만하면 long을 쓰자

 

4. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    public static final int MOD = 1_000_000_009;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static long dp [][] = new long[100_000+1][4];

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

        int T = Integer.parseInt(br.readLine());       // 테케 개수

        solution();
        for(int i=0; i<T; i++){
            int n = Integer.parseInt(br.readLine());
            bw.write(getAnswer(n)+"\n");
        }
        bw.flush();
    }

    public static void solution(){
        dp[1][1] = dp[2][2] = 1;
        dp[3][1] = dp[3][2] = dp[3][3] = 1;

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

    public static long getAnswer(int n){
        return (dp[n][1] + dp[n][2] + dp[n][3]) % MOD;

    }

}