글 읽기 - 두개의 차이를 모르겠습니다

kksy2423 2년 전 0

35~37번째 줄을

arr[i][1]=((arr[i-1][2]+arr[i-1][3]))%mod;

arr[i][2]=((arr[i-2][1]+arr[i-2][3]))%mod;

arr[i][3]=((arr[i-3][1]+arr[i-3][2]))%mod;

와 같이 고쳤더니 정답이 되는데 전체에서 안되는경우를 뺀것이랑 되는경우 두가지를 더하는 경우로 나누었다고 생각하는데

두개가 왜 다른지 모르겠습니다.... ㅠㅠ

#include<iostream>

using namespace std;

const long long mod = 1000000009;

int main(){
    
    long long arr[1000001][4];
    
    int TestCase;
    
    cin>>TestCase;
    
    long long dp[100001];
    
    dp[1]=1;
    arr[1][1]=1;
    
    dp[2]=1;
    arr[2][2]=1;
    
    dp[3]=3;
    arr[3][1]=1;
    arr[3][2]=1;
    arr[3][3]=1;
    
    for(int i=4;i<=100001;i++){
        
        arr[i][1]=((dp[i-1]-arr[i-1][1]))%mod;
        arr[i][2]=((dp[i-2]-arr[i-2][2]))%mod;
        arr[i][3]=((dp[i-3]-arr[i-3][3]))%mod;
        
        dp[i]=(arr[i][1]+arr[i][2]+arr[i][3])%mod;
        
    }
    
    //TestCase를 받고 시작
    for(int i=0;i<TestCase;i++){
        int a;
        cin>>a;
        cout<<dp[a]<<'\n';
    }
}

yous 2년 전 1

arr와 dp에 값을 넣으면서 mod를 하고 있기 때문에 dp에 들어있는 값이 arr 하나의 값보다 작을 수 있습니다. 음수에 mod를 취하면 원하는 값이 나오지 않을 수도 있습니다.

arr[i][1] = (dp[i - 1] - arr[i - 1][1] + mod) % mod;

같은 형태라면 될 것 같네요.

kksy2423 2년 전 0

감사합니다 덕분에 이해가 된거같습니다.

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

문제

문제

출처

ICPC

두개의 차이를 모르겠습니다

kksy2423 2년 전 0

yous 2년 전 1

kksy2423 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말