[백준] 2560 : 짚신벌레 (파이썬)

DP, 누적합 문제

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

 

---

접근 방식 

• 문제를 단순화해서 생각해보자.
  우리가 구해야하는 값은 N일째 되는 날 살아있는 짚신벌레 수(를 1000으로 나눈 나머지)이다.
  그러면 dp에 무슨 값을 기록해야할까 ? -> for문을 N번 돌며 dp[i]에 i일에 살아있는 짚신벌레 수를 기록하자.
• 참조해야 하는 배열 없이, 이전 dp 배열에 기록했던 짚신벌레 수를 활용하여 현재 dp 배열의 값(현재 i일째에 살아있는 짚신벌레 수)를 구할 수 있다.
• dp[i]는 i일째 되는 날에 살아있는 짚신벌레의 수

---

💡 풀이코드 (성공)

import sys 
a, b, d, N = map(int, sys.stdin.readline().split())

def sol(a, b, d, N):
    dp = [0] * (N + 1)

    # 초기화
    for i in range(a):
        dp[i] = 1
    
    # a ~ b 번식
    for i in range(a, N + 1):
        dp[i] = (dp[i - 1] + dp[i - a]) % 1000

        if i >= b:
            dp[i] = (dp[i] - dp[i - b]) % 1000
    
    # 죽은 벌레
    if N >= d: # 에외 처리
        print((dp[N] - dp[N - d]) % 1000)
    else:
        print(dp[N] % 1000)
        
sol(a, b, d, N)

 

핵심로직

1. 초기화

 

성체가 되기 전인 a일 이전까지는 처음 수조에 넣은 짚신벌레 한 마리만 존재한다.

따라서, dp[0]부터 dp[a-1]까지의 값은 모두 1로 설정한다.

 

2. 번식 계산 (누적합 O )

a일째부터는 번식이 시작되므로, 매일 새로운 개체가 추가된다.

dp[i]는 전날의 짚신벌레 수인 dp[i-1]에 a일 전에 태어난 짚신벌레들이 성체가 되어 번식한 짚신벌레 수 dp[i-a]를 더한 값이다.

 

 

3. 번식 종료 (누적합 O)

b일 이후부터는 번식이 멈추기 때문에, b일 전에 태어난 짚신벌레는 더 이상 번식하지 않는다.

b일 이상 지난 날의 경우, b일 전에 태어난 짚신벌레가 만든 개체 수를 빼준다.

 

 

4. 죽음 계산 (누적합 X)

d일째부터는 짚신벌레가 죽는다. N일째가 d일 이상이면, d일 전에 태어난 짚신벌레는 모두 죽기 때문에 N−d일째의 짚신벌레 수를 빼준다.

 

• 4번에서 죽음 계산은 누적합을 사용하지 않는 이유는 단순히 죽은 개체 수를 빼는 것이기 때문이다. 
• 번식 계산과 종료는 매일의 변화(번식)를 누적해야 하지만, 죽음 계산은 단순히 특정 날의 개체 수를 직접 빼는 작업이다.

 

예시

---

느낀점

 

막연하게 DP 점화식을 찾으려하지 말고, 문제를 꼼곰히 읽은 후 주어진 정보를 잘 활용하자 ..

 

참고문헌

https://4legs-study.tistory.com/101

[DP] BOJ 2560 짚신벌레

https://latter2005.tistory.com/76

[백준] 2560 짚신벌레

https://ujajuck.tistory.com/6

짚신벌레 1822 (백준 2560)

https://rccode.tistory.com/270

[Python] 백준 2560번: 짚신벌레