[BOJ] 백준 2560 : 짚신벌레 (java)

• 🧪 2560 짚신벌레

• 📝 문제

• 🚧  주의할 점

• 🧐 핵심 로직

• 💻 최종 코드 (124 ms)

🧪 2560 짚신벌레

---

난이도 : 🌟 골드 3
유형 : 누적합

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

 

📝 문제

---

한 생물학자가 새로 발견된 짚신벌레 종의 생태에 대해 연구하고 있다. 매우 번식력이 강하다고 알려진 이 종은 아래와 같은 특징을 가지고 있다.

무성 생식을 한다.

• 태어난 이후 a일째 되는 날 성체가 된다.
• 성체가 된 날부터 매일 한 마리씩 새로운 개체를 만들어낸다: 성체가 되자마자 첫 개체를 만들어내고, 그 이후로 하루가 지날 때마다 새로운 개체를 하나씩 만들어낸다. 새로운 개체 역시 태어난 이후로 a일째 되는 날부터 성체가 되어 새로운 개체를 만든다.
• 태어난 이후로 b일째 되는 순간부터는 새로운 개체를 더 이상 만들지 않는다. 태어난 지 a일째 날부터 b일째 되는 날의 전날까지 새로운 개체를 만들어내므로 일생동안 총 b-a 마리의 개체를 만들어낸다.
• 태어난 이후로 d일째 되는 순간 죽는다.

아래는 a=2, b=4, d=6일 때 수조에 새로 태어난 짚신벌레 한 마리를 넣고 매일 관찰한 결과를 기록한 것이다. 괄호 안의 숫자들은 수조 안의 짚신벌레들이 각각 태어난 이후 며칠이 되었는지를 나타내는 정수이다.

• 태어난 날: (0) - 새로운 개체를 집어넣음
• 1일째 되는 날: (1) - 짚신벌레가 자람
• 2일째 되는 날: (2, 0) - 짚신벌레가 태어난 지 2일째가 되므로 성체가 되고 새 개체를 만들어 냄
• 3일째 되는 날: (3, 1, 0) - 2일째 성체가 된 짚신벌레가 오늘도 새 개체를 하나 만들어 냄
• 4일 째 되는 날: (4, 2, 1, 0) - 2일째 되는 날 만들어진 짚신벌레가 새로운 개체를 만들어 냄 (처음에 넣은 짚신벌레는 새 개체를 만들어내지 못함)
• 5일 째 되는 날: (5, 3, 2, 1, 0, 0)
• 6일 째 되는 날: (4, 3, 2, 1, 1, 0, 0) - 처음에 넣은 개체는 죽는다.

6일 째 되는 날 수조안에 살아있는 짚신벌레는 총 7마리가 된다.

짚신벌레의 번식 정보 a, b, d에 대하여, 새로 태어난 짚신벌레 한 마리를 수조 안에 넣은 이후 N일째 되는 날 살아있는 짚신벌레 수를 1000으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d ≤ 10,000이고, 1 ≤ N ≤ 1,000,000이다.

 

출력

 

첫째 줄에, 수조에 짚신벌레 한 마리를 넣은 지 N일째 되는 날 수조에 살아 있는 짚신벌레의 수를 1000으로 나눈 나머지를 출력한다.

 

🚧  주의할 점

---

• 모듈러 연산: 점화식에서 계산 결과를 항상 1000으로 나눈 나머지로 저장하기 때문에, 값이 1000 범위 안에 머물도록 관리해야 한다.
• 음수 방지: 점화식에 뺄셈이 포함되어 있어 계산 도중 음수가 발생할 수 있다. 이 경우, +1000을 추가하여 양수로 만든 뒤 %1000을 수행하면 음수 문제를 방지할 수 있다.

🧐 핵심 로직

---

1. 입력값으로 들어온 a, b, d, n 값을 저장한다.

 

2. dp 배열을 생성하고, 초기값으로 dp[0] = 1을 설정한다.

 

3. 1일부터 n일까지 반복문을 실행하며, 각 일자의 점화식을 계산한다.

    3 - 1) 현재 날짜가 a보다 작으면, 이전 날까지의 결과값 dp[i-1]만을 저장한다.

    3 - 2) 현재 날짜가 b보다 작으면, 이전 날의 값과 a일 전에 번식한 결과값을 더해 저장한다.

    3 - 3) 현재 날짜가 b 이상이면, 이전 날의 값과 a일 전에 번식한 값, 그리고 b일 전에 번식이 끝난 값을 더하고 빼서 저장한다. 이 과정에서 음수를 방지하기 위해 +1000을 더하고 %1000을 수행한다.

 

4. 계산이 완료된 후, n-d 이상까지 누적된 값과 n-d 이전의 값을 비교하여 결과를 출력한다.

    4 - 1) 만약 n-d가 0 이상이면, dp[n] - dp[n-d] 값을 출력한다.

    4 - 2) 그렇지 않으면, dp[n] 값을 출력한다.

 

5. 모든 입력과 계산이 완료되면 프로그램을 종료한다.

 

💻 최종 코드 (124 ms)

---

import java.util.*;
import java.io.*;

public class Main {

    static int a, b, d, n;
    static int[] dp;
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (i < a) {
                dp[i] = dp[i - 1] % 1000;
            } else if (i < b) {
                dp[i] = (dp[i - 1] + dp[i - a]) % 1000;
            } else {
                dp[i] = (dp[i - 1] + dp[i - a] - dp[i - b] + 1000) % 1000;
            }
        }

        if (n - d >= 0) {
            System.out.println((dp[n] - dp[n - d] + 1000) % 1000);
        } else {
            System.out.println(dp[n] % 1000);
        }

        br.close();
    }
}