99클럽 코테 스터디 22일차 TIL + 다이나믹 프로그래밍(DP)

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "멀리 뛰기" 문제를 풀었다.
- 오늘도 DP(다이나믹 프로그래밍) 문제인데 조건이 어제와 하나 달랐다.

[나의 코드]

def solution(n):
    d = [0] * (n + 1)
    d[1] = 1
    
    if n > 1:
        d[2] = 2
    
    for i in range(3, n + 1):
        d[i] = d[i - 1] + d[i - 2]
    
    return d[n] % 1234567

어제의 문제와 달리 점화식을 직접 찾아야 했다.
근데 이 정도 문제는 점화식을 쉽게 구할 수 있고, 무려 어제 피보나치 문제와 같다.

d[1] = 1 → 경우의 수가 하나밖에 없다.
d[2] = 2 → 얘는 두 개뿐이다.
d[3], d[4]는 문제에서 주어져있다.
d[3] = 3 
d[4] = 5
d[5] = 8 → 손으로 직접 그리면 8개임을 알 수 있다.

그래서 점화식으로 식을 이렇게 쓸 수 있다.
d[i] = d[i - 1] + d[i - 2]

하지만 어제와 다른 조건이라면, 피보나치 문제는 n이 2부터 시작했는데, 이 문제는 1부터 시작한다.
어쩐지 테스트 케이스 1번만 오류가 나더라. 그래서 n이 2 이상일 때만 d[2]에 값을 넣어준다.

[오늘의 회고]
- 고수들의 생각 회로를 구경하고 왔는데, 문제에서 '한 번에 1칸, 또는 2칸'이 부분을 읽고 바로 DP를 떠올렸다고 한다.
- 다른 DP 문제를 더 풀어보고 와야겠다.
- 근데 개인적으로 다이나믹 듀오 노래는 BAAAM이 제일 익숙하다. (세대 차이 ^^)
- 피처링한 노래까지 하면 아닐지도? 끝!