[백준] 15988 - 1,2,3 더하기 3 (Java)

[백준] 15988 - 1,2,3 더하기 3 (Java)

문제

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

풀이/후기

이것 또한 9095 문제를 풀었다면 점화식은 동일하게 사용할 수 있다.

근데 몇 번을 제출해도 계속 오답처리가 됨.

포인트는 자료형이었는데,

처음에 인식하고 있었으나 Integer.MAX_VALUE 값을 찍어보니 문제에서 다루는 수가 더 적은 것 같아서 int를 사용해서 틀린 것.

(당연하지 연산 결과가 훨씬 크게 나오는데 난 무슨 생각을 한걸까?)

아무튼 자료형을 long으로 바꿔주면 아주 편안해진다

 

그리고 실행시간이 좀 걸리길래 코드를 좀 수정했는데

dp 반복문은 어차피 N과 별도로 실행되어도 되는 부분이므로

테스트케이스 돌아가는 반복문 밖에서 실행하고

해당 반복문 안에선 출력만 하면 된다.

코드

package DynamicProgramming;

import java.io.*;

public class Problem15988 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		long[] dp = new long[1000000 + 1];

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

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

		while (T-- > 0) {
			int N = Integer.parseInt(br.readLine());
			sb.append(dp[N]).append("\n");
		}
		
		System.out.println(sb);

	}

}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/b217b638517c1a114be410e270c7bdcbf4caa909

참고