📍 문제

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

💻 답안코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        if (n == 1) {
            bw.write("1");
            bw.flush();
            bw.close();
            br.close();
            return;
        }

        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i <= n; i++){
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }

        bw.write(String.valueOf(dp[n]));
        bw.flush();
        bw.close();
        br.close();
    }
}

💡

처음에는 배열에 값을 우선 다 넣어준 뒤, 10007 로 나눈 값을 출력하였다.
int answer = dp[n] % 10007 ; 요렇게 . .
틀렸습니다 ! 가 떠서 배열에 넣을 때부터 10007 로 나눈 값을 넣어주니 정답 처리가 되었다.

배열에 값을 넣어줄 때 나머지를 먼저 구하는 이유

dp[i - 1]와 dp[i - 2]가 이미 매우 큰 값일 수 있다.
예를 들어, dp[i] = 1000000 이라면 문제에서 요구한 범위를 벗어나게 된다.
만약 이 값을 나머지 연산 없이 먼저 배열에 넣은 후 나중에 나머지 값을 구하려고 하면, 결국 결과값이 너무 커져서 메모리 초과나 오버플로우가 발생할 수 있다.
따라서 배열에 넣어주는 중간 계산에서 먼저 나머지 값을 구해주면, 계산이 커지는 것을 방지하고 값의 범위를 제어할 수 있다 !

문제에서 10007 이라는 수를 사용한 이유도 찾아보았다 !

처음 문제를 시도할 때 10007 이라는 수에 대해 궁금했었는데 메모리 초과, 오버플로우 방지를 위한 것임을 알았으니 다음 문제를 풀 때 이러한 경우를 마주한다면 좀 더 빠르게 접근할 수 있을 것 같다 !