백준 짚신벌레(2560)

짚신벌레

1. 힌트

1) $S[i] =i$번째 날에 새로 태어난 짚신벌레의 수로 정의하면 $S[i] = \displaystyle\sum_{k=a}^{b-1}S[i-k],(S[0]=1)$입니다. 문제의 정답은 $\displaystyle\sum_{k=0}^{d-1}S[N-k]$가 됩니다.

2) 누적합 배열을 정의해서 $P[i] = \displaystyle\sum_{k=0}^iS[k]$로 정의하면 $S[i] = P[i - a] - P[i - b]$입니다.

3) 나머지 연산 과정에서 음수가 되지 않도록 유의합니다.

2. 접근

1) 점화식

문제에서 원하는 답처럼 $S[i] = i$번째 날 살아있는 짚신벌레 수로 정의하면 이 $S[i]$를 가지고 $S[i + 1]$을 만들어낼 수 없기 때문에 점화식의 정의를 조금 바꾸어보겠습니다.

$S[i] =i$번째 날에 새로 태어난 짚신벌레의 수로 정의하면 $S[i] = \displaystyle\sum_{k=a}^{b-1}S[i-k],(S[0]=1)$입니다. $i - a$번째 날에 태어난 짚신벌레들은 $i$번째 날 부터 새 개체를 만들어 낼 수 있고, $i - (b - 1)$번째 날에 태어난 짚신벌레들 까지 새로운 개체를 만들어 낼 수 있기 때문입니다.

이렇게 $S[i]$를 모두 구해놨다면 우리가 원하는 문제의 정답은 $\displaystyle\sum_{k=0}^{d-1}S[N-k]$가 됩니다. $N - (d - 1)$번째 날부터 태어난 개체들은 $N$번째 날에 살아있고, 그 전에 태어난 개체들은 모두 죽었기 때문입니다.

2) 누적 합

위에서 정의한대로 점화식을 채워 넣는다면 그 과정의 시간 복잡도는 $O(N\times 10000)$입니다. $S[i]$의 점화식은 부분 합으로 정의되어있으므로 $O(N)$의 전처리를 통해 누적 합 배열을 만들어주면 부분 합을 $O(1)$에 구할 수 있습니다.
$P[i] = \displaystyle\sum_{k=0}^iS[k]$로 정의하면 $S[i] = P[i - a] - P[i - b]$입니다. 따라서 우리가 원하는 문제의 정답은 $P[N] - P[N - d]$가 됩니다

3. 구현

1) 누적 합 배열 P

$P[i] = P[i - 1] + P[i - a] - P[i - b]$입니다. 누적 합 배열의 정의도 일종의 점화식으로 이해할 수 있습니다.

2) 나머지 연산

나머지 연산 과정에서 덧셈이면 상관 없지만 뺄셈인 경우 결과가 음수가 될 수 있습니다. 따라서 안전하게 중간 중간에 MOD값을 더해줍니다.

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder bw = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] P = new int[N + 1];
        P[0] = 1;
        for (int i = 1; i <= N; i++) {
            P[i] = P[i - 1];
            if (i - a >= 0) P[i] = (P[i] + P[i - a] + 1000) % 1000;
            if (i - b >= 0) P[i] = (P[i] - P[i - b] + 1000) % 1000;
        }
        int sum = P[N];
        if (N - d >= 0) sum = (sum - P[N - d] + 1000) % 1000;
        bw.append(sum).append("\n");
        System.out.print(bw);
    }

}

3) 시간 복잡도

$O(N)$