글 읽기 - 중간에 %1000000009 하는 이유가 뭔가요?

devhyun46 2년 전 0

맨 마지막에 %1000000009도 하는데

중간에도 15~17줄에서도 %1000000009 이 연산을 하잖아요.

그게 %1000000009을 안하면 long범위를 벗어나서 그런거라고 듣긴했는데

그걸 제가 어떻게 판단하나요? i의 최대수인 dp[100000]을 직접 구할 수도 없고.. 그게 넘어가는지 안넘어가는지

다른 분들은 어떻게 판단하셨는지 도움 좀 부탁드려요!

import java.io.*
import kotlin.math.*
import java.util.*

fun main()=with(BufferedReader(InputStreamReader(System.`in`))) {
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    var n = readLine().toInt()
    var dp = Array(100001){LongArray(4)}
    dp[1][1] = 1
    dp[2][2] = 1
    dp[3][1] = 1
    dp[3][2] = 1
    dp[3][3] = 1
    for(i in 4..100000){
        dp[i][1] = (dp[i-1][2]+dp[i-1][3])%1000000009
        dp[i][2] = (dp[i-2][1]+dp[i-2][3])%1000000009
        dp[i][3] = (dp[i-3][1]+dp[i-3][2])%1000000009
    }
    repeat(n){
        var s = readLine().toInt()
        bw.write("${(dp[s][1]+dp[s][2]+dp[s][3])%1000000009}\n")
    }
    bw.flush()
}

becl3ver 2년 전 0

코틀린은 잘 모르지만 넘는지 확인하시고 싶으시면 중간에 모듈러를 빼고 n의 범위만큼의 임의의 값을 증가시키면서 넣어서 오버플로우가 발생하는지 확인해보세요

모듈러 연산은 분배법칙이 성립하니까 비슷하게 모듈러한 값을 구하는 문제이면 그냥 중간중간에 최대한 많이 넣어주는게 좋을거 같네요

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

문제

문제

출처

ICPC

중간에 %1000000009 하는 이유가 뭔가요?

devhyun46 2년 전 0

becl3ver 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말