[BOJ] 2193. 이친수

Python3,DP

문제

입출력

입출력 예시

나의 풀이 (시도)

n = int(input())
dp = [0] * 10
dp[1] = 1
dp[2] = 1

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

print(dp[n])

이렇게 했더니 Index 오류가 났다. n이 1일 때 조건을 처리해주어야 한다. DP 문제는 n이 1일 때 처리 해주는 조건을 많이 요구한다고 한다.. 참고하기

주요 포인트

1 => 1
10 => 1
100, 101 => 2
1000, 1001, 1010 => 3
10000, 10001, 10010, 10100, 10101 => 5

이런 식으로 dp[i-1] + dp[i-2] 규칙을 찾을 수 있다.

최종 코드

n = int(input())

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

    print(dp[n])

입력값으로 1이 들어 왔을 때를 분리했다.
n+1개의 0으로 dp가 세팅되도록 해주었고, 반복문 역시 n까지 돌도록 바꿨다.

• 23/5/10 추가

n = int(input())

dp = [1 for _ in range(91)]

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

어차피 dp[1], dp[2]는 1이라서 dp를 모두 1로 초기화하고 3부터 반복문을 시작한다.

다른 사람 풀이

n = int(input())
dp = [0, 1, 1]

for i in range(3, 91):
    dp.append(dp[i-1] + dp[i-2])

print(dp[n])

dp를 0, 1, 1로 초기화해주고 append 함수를 통해 dp 배열에 값을 넣었다.

피드백

드디어 규칙은 찾았다. 패턴을 빨리 찾은 부분은 좋았다.
n이 1일 때의 조건을 나누기에 대해 또 하나 더 배웠다.