백준 - 리그 오브 레전설 (Small) 풀이 정리

1. 우리가 원하는 건 “합이 정확히 nnn이 되는 A, B 조합”이옵니다.
   • A = 1, B = m
   • 즉, 한 칸에는 A(1) 또는 B(m)이 들어갈 수 있음.
2. 그러므로 dp[x] = “합이 x가 되는 문자열 조합의 수” 라고 정의할 수 있사옵니다.
3. 점화식:
   • 마지막에 A(=1)을 넣었다면, 이전 합은 x−1x-1x−1.
   • 마지막에 B(=m)을 넣었다면, 이전 합은 x−mx-mx−m.
   • 따라서dp[x]=dp[x−1]+dp[x−m]dp[x] = dp[x-1] + dp[x-m]dp[x]=dp[x−1]+dp[x−m](단, 인덱스가 0 이상일 때만 더함)
4. 초기 조건:
   • dp[0] = 1 (아무것도 선택하지 않은 경우 하나).
   • 나머지는 0으로 시작.
5. 최종 답: dp[n].

---

작은 예시

• n=3,m=2n=3, m=2n=3,m=2
  • dp[0] = 1
  • dp[1] = dp[0] = 1 → "A"
  • dp[2] = dp[1] + dp[0] = 1 + 1 = 2 → "AA", "B"
  • dp[3] = dp[2] + dp[1] = 2 + 1 = 3 → "AAA", "AB", "BA"
    ✅ 답: 3

---

코드

# import sys
# sys.setrecursionlimit(10**6)

# n, m = map(int, input().split())

# A = 1
# B = m

# results = []
# def backtrack(current, total):
#     if total == n:
#         results.append("".join(current))
#         return
#     if total > n:   
#         return
    
#     backtrack(current + ["A"], total + A)
#     backtrack(current + ["B"], total + B)

# backtrack([], 0)

# print(len(results) % 1000000007)

n, m = map(int, input().split())

A = 1
B = m

dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n + 1):
    if i < m:
        dp[i] = dp[i - 1]
    else:
        dp[i] = dp[i - 1] + dp[i - m]

print(dp[n] % 1000000007)

 

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