글 읽기 - 점화식 맞지 않나요...? 왜 틀렸다고 뜨는지 모르겠습니다.

kjy9718998 7년 전 1

다이나믹 프로그래밍으로 다음과 같이 프로그래밍 했는데, 4%에서 틀렸습니다 뜹니다.

점화식이 틀린걸까요..??

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long[] dp = new long[n+1];
         
        dp[0] = 1;
        dp[1] = 3;
        for(int i=2; i<dp.length; i++){
            dp[i] = dp[i-2]+dp[i-1]*2;
        }
         
        System.out.println(dp[n]%9901);
    }
 
}

exqt 7년 전 0

반복분 안에 dp[i] = dp[i] % 9901;

를 추가해주시면 됩니다.

kjy9718998 7년 전 0

exqt님 댓글 감사합니다!!

말씀해주신 것처럼 바꾸니까 해결은 됐는데,

왜 dp[n]%9901을 출력하는 것은 안되고,

매번 dp[i]값을 9901로 나눈 나머지 값으로 갱신해야하는지 잘 모르겠습니다ㅠ

dokrsky 7년 전 0

dp[n]을 구하는 과정에서 9901을 초과할 수도있으니까요

가령, 예를들어 dp[n-3]에서 9904가 나왔다고 했을 땐 dp[n-3] = 9904 % 9901 을 해주어야 하니까용

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

문제

문제

출처

ICPC

점화식 맞지 않나요...? 왜 틀렸다고 뜨는지 모르겠습니다.

kjy9718998 7년 전 1

exqt 7년 전 0

kjy9718998 7년 전 0

dokrsky 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말