[#2193] 이친수

문제

#2193 이친수
Silver3
적용 알고리즘: 다이나믹 프로그래밍

---

풀이 방법

• 하나의 큰 문제를 여러문로 나누어 생각해야 한다. 이때, 중복이 가능한 문제여야 DP가 적용 가능하다. 이 문제에서는 이전 값을 기록해두는 메모이제이션 기법을 사용하였다.
• 가장 최소 단위부터 시작하여 하나씩 올라가며 답을 구해보고, 이 과정에서 각 절차간의 관계를 파악한다.
• 도출한 규칙으로 점화식을 만든다. (보통 1, 2 (많으면 3까지는)는 상수인것 같다…)
• 1이 중복으로 올 수 없고, 첫번째 자리는 필수로 1이 와야 하기 때문에 두번째 자리의 값은 무조건 0이 된다. 입력한 자리수가 n이라면, (첫번째와 두번째의 값이 이미 정해져 있기 때문에) n-2 자리만 고려하면 된다.

코드 흐름

1. 입력되는 값의 범위가 최대 90까지이므로 길이 90의 배열을 생성한다.
2. 1, 2인경우 답은 1이다. (k[1] = 1)
3. 3인 경우 마지막 세번째 자리의 값만 고려하면 된다. 세번째자리는 k[1]와 해당 자리가 0인 경우(1개)의 합인 2개이다. (k[3] = k[1] + 1)
4. 4인 경우 세번째, 네번째 자리의 경우만 고려하면 된다. (k[4] = k[2] + k[1] + 1)
5. 점화식은 k[n] = k[n-2] + k[n-3] + k[n-4] + k[n-5] + … + 1(전부 다 0인 경우)이지만, k[3] = k[1] + 1 로 치환하면 결국 k[n] = k[n-1] + k[n-2]가 된다.

코드

k = [0] * 91
k[1] = 1
k[2] = 1

for i in range(3, 91):
    k[i] = k[i - 1] + k[i - 2]

n = int(input())
print(k[n])

체감 난이도: 4.2/5
내가 걱정한 것보다는 문제가 쉽게 풀었다. 1부터 시작해서 2, 3, … 답을 구하기 시작했고, 결국 규칙을 알아냈다. 차근차근하게 풀어보니 문제는 풀었지만, 이 문제의 유형이 DP인걸 알지 못했다면 점화식을 세울 생각조차 하지 못했을 것 같다… 일단 공책을 펴고 연필로 뭐라도 끄적거리는 것이 가장 중요한 것 같다.