글 읽기 - 문제가 이해가 잘 안가요ㅠㅠ

areumchoi19 5년 전 0

n값이 워낙 크다보니 dp 배열에 넣는 과정에서 int 범위를 넘어가버리네요!!

그래서 출력부분에 1,000,000,009로 나눈 나머지를 출력하라고 되어있는 것같았는데 아닌가봐요ㅠㅠ

dp배열에 dp[i-1] + dp[i-2] + dp[i-3] 값을 1,000,000,009로 나눈 나머지를 넣도록 했더니 틀렸다고 나와서요ㅠㅠ

import java.io.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test_num, max = 0;
		int[] input_num;
		int[]dp;
		test_num = new Integer(br.readLine());
		input_num = new int[test_num];
		
		for(int i=0; i<test_num; i++) {
			input_num[i] = new Integer(br.readLine());
			max = max>input_num[i] ? max : input_num[i];
		}
		dp = new int[max+1];
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		
		for(int i=4; i<=max; i++) {
			dp[i] = (dp[i-1] + dp[i-2] + dp[i-3])%1000000009;
		}
		for(int i=0; i<test_num; i++) {
			System.out.println(dp[input_num[i]]);
		}
	}
}

2a2aq 5년 전 1

제 추측으로는 dp[i-1] + dp[i-2] + dp[i-3] 값이 int 범위를 벗어나는 것 같습니다. int 대신 long long 배열을 사용해야 할 것 같아요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제가 이해가 잘 안가요ㅠㅠ

areumchoi19 5년 전 0

2a2aq 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말