[DP 연습] BOJ_15988 1, 2, 3 더하기 3 (S2)

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

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

 

1이랑 별반 다른 문제가 아닌 것 같아서 이상하다는 생각이 들었어도 그대로 짰는데, 계속계속 틀렸다고 떠서 빡쳤다. 대체 뭐가 문제지 싶어서 구글링을 해봐도 단지 배열을 선언해준 크기와 타입이나 위치만 다른 것 같은데 크게 문제될 게 없을 것 같은데 왜 자꾸 틀렸다고 하지 싶었다. 그런데 https://c-king.tistory.com/280 이분 글을 읽어보니까, 10억으로 나눈 나머지를 출력한다는 부분이 문제의 함정같은 것이고,  이 말인 즉슨10억이 넘는 곳이 있다는 뜻이기 때문에 배열의 범위를 int로 해주면 안되고 long으로 선언해줘야 한다는 것이였다. 그리고 mod를 나눠줘야 하는 건 어제 대충 이해를 했는데, 숫자의 범위가 너무 커지기 때문에 나머지정리 느낌으로 숫자의 크기를 줄여주는 개념인 것 같다. 그렇게 하지 않으면 overflow 가 발생해서 이상한 값이 저장되기 때문에!

 

아무튼 그래도 아직도 이해되지 않는 의아한 부분은,

testcase 반복문을 전체로 감싸면 아래처럼 시간초과가 나는 부분이였다. 왜인지 모르겠다..

 

넘어야 할 산이 참 많은데 시간은 촉박한 느낌이다!

 

 

 

1,2,3 더하기 1

1,2,3 더하기 3

 

package algo0923;

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

// 1,2,3 더하기 3
public class BOJ_15988 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			
			int N = Integer.parseInt(br.readLine());
			
			int[] dp = new int[N+1];
			
			dp[0] = 0;
			dp[1] = 1;
			dp[2] = 2;
			dp[3] = 4;
			
			for (int i = 4; i <= N; i++) {
				dp[i] = (dp[i-1] + dp[i-2] + dp[i-3])%1000000009;
			}
			sb.append(dp[N]).append("\n");
		}
		System.out.println(sb.toString());
	}
}

package algo0923;

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

// 1,2,3 더하기 3
// https://c-king.tistory.com/280
public class BOJ_15988_sol {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		int mod = 1000000009;
		int size = 1000000;
		
		long[] dp = new long[size+1];
		
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		
		for (int i = 4; i <= size; i++) {
			dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % mod;
		}
		
		for (int t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine());
			sb.append(dp[N]).append("\n");
		}
		System.out.println(sb.toString());
	}
}

// 의아한 부분에 대한 코드
// testcase 반복문으로 전체를 감싼 시간초과가 발생한 코드

package algo0923;

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

// 1,2,3 더하기 3
// https://c-king.tistory.com/280
public class BOJ_15988_sol2 {
	public static void main(String[] args) throws NumberFormatException, IOException {

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

		int T = Integer.parseInt(br.readLine());
		int mod = 1000000009;
		int size = 1000000;

		for (int t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine());

			long[] dp = new long[size + 1];

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

			for (int i = 4; i <= size; i++) {
				dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
			}
			sb.append(dp[N]).append("\n");
		}
		System.out.println(sb.toString());
	}
}