짚신벌레 1822 (백준 2560)

문제 링크

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1095&sca=3060 

JUNGOL

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

2560번: 짚신벌레

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 br=new BufferedReader(new InputStreamReader(System.in));
		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());
		long[] dp=new long[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)%1000;//1마리가 번식
			else dp[i]=(dp[i-1]+dp[i-a]-dp[i-b]+1000)%1000;//낳은 자식들이 번식
		}
		//점화식에 뺄샘이 들어있어 모듈러 연산중 값이 음수가 될 수 있기 때문에 mod 만큼 더해 이를 방지한다.
		if(n-d>=0)System.out.println((dp[n]-dp[n-d])%1000);
		else System.out.println(dp[n]%1000);
	}
}

 

풀이 

첫번째 짚신 벌레가 번식을 시작한 이후

 

오늘=전날+(오늘부터 b-a이전에 태어난 벌래(즉 오늘 성인인것))

dp[i]=(dp[i-1]+dp[i-a]-dp[i-b]+1000)%1000

 

마지막에 오늘까지 짚신벌레 - 오늘부터 d일 이전에 살아있었던 것 = 오늘의 짚신벌레

System.out.println((dp[n]-dp[n-d])%1000);

 

+ ) 모듈러 연산의 성질

(a+b+c)%m=a%m+b%m+c%m

1000%1000==0 이므로 답은 변하지 않는다. 

dp[i-a]-dp[i-b]<0 일 수 있으므로 +1000을 해준다.