[BOJ] 백준 2560번 짚신벌레 - Java

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

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으로 나눈 나머지를 출력한다.

 

풀이

a일 부터 무성생식이 가능하므로 a까지는 1마리로 유지된다. 이후로 b일까지 생식을 진행하므로 계속 증가한다. 이때 b일 전까지의 벌레의 마리수는 전날 + 오늘 새로 태어난 벌레의 수이다. 그래서  dp[i] = dp[i-1] + dp[i-a] 이다. 

오늘 태어난 벌레의 수는 오늘 부터 a일 전에 있던 벌레의 수이다.

 

하지만 b일 이후에는 더이상 생식을 하지 않기에 b일 이후의 벌레는 dp[i] = dp[i - 1] + dp[i - a] - dp[i - b] 이다. 이렇듯 더이상 생식을 하지 않은 벌레 수를 빼주면서 더해간다.

 

그리고 d일 이후에는 죽은 벌레의 수를 빼주면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        int death = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] dp = new int[N+1];
        dp[0] = 1;

        for (int i = 1; i <= N; i++) {
            if (i<start) // 시작날 전까지 유지됨.
                dp[i] = dp[i-1]%1000;
            else if(i<end) // 단순하게 증가함! 전날 + 새로 태어남
                dp[i] = (dp[i-1] + dp[i-start])%1000;
            else
                dp[i] = (dp[i-1]+dp[i-start]-dp[i-end]+1000)%1000;
        }

        if(N-death>=0)
            System.out.println((dp[N]-dp[N-death]+1000)%1000);
            
        else System.out.println(dp[N]%1000);

    }
}