[TIL] 99클럽 코테 스터디 15일차 TIL + DP

🌼 오늘의 문제 - 백준 17271. 리그 오브 레전설 (Small)

아직 DP, 누적합 등을 고려해야 한다는 사실까지는 알아도, bottom up으로 생각해야 한다는 것을 떠올리기까지 시간이 좀 걸리는 것 같다. 이 문제는 싸우는 시간 n 안에서 1초 걸리는 스킬 A와 m초 걸리는 스킬 B의 경우의 수를 찾는 문제다. n은 자연수이므로 싸우는 시간이 1초일 땐, 경우의 수 1. 2초일 때부터는 m의 값을 고려하게 된다. 일단, 이전 스킬에서 A를 더하는 경우와 B를 쓰기 위해 m초 전 경우의 수를 더하면 된다. 결국 점화식이라는 의미인데, 이 말을 식으로 쓰면 dp[i] = dp[i - 1] + dp[i - m] 이 된다. 이 내용만 잘 고려하면 금방 풀 수 있다. (나는 반복문의 시작을 m으로 두지 않는 실수를 해서 한 번 틀렸다..)

# n: 싸움 시간, m: B 시간
n, m = map(int, input().split())

# dp[1] = 1
dp = [1] * (n + 1)

# dp[2] = dp[1] AA B
# dp[3] =  AAA AB BA
# dp[4] =  AAAA ABA BAA AAB BB
# dp[5] =  AAAAA ABAA BAAA AABA BBA AAAB ABB BAB
for i in range(m, n + 1):
    dp[i] = (dp[i - 1] + dp[i - m]) % 1000000007

print(dp[n])