백준 2579 파이썬(DP)

 

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

2579번: 계단 오르기

문제의 조건은 세가지다.

1. 연속된 세개의 계단을 밟으면 안됨

2. 마지막 계단은 밟아야함

3. 한칸 또는 두칸씩 이동 가능함.

 

마지막 계단은 밟아야하므로

i번째 계단이라고 한다면

 

max(i-2번째 계단을 밟고 두칸을 뛰어 i번째로 온 경우, i-3번째 계단을 밟고 i-1번째를 밟고 i번째로 온 경우)

이런식으로 점화식을 만들면 된다.

 

• 코드

# 2579 - 계단 오르기

n = int(input())
steps = []
for _ in range(n):
    steps.append(int(input()))

res = [0] * (n)

res[0] = steps[0]
res[1] = steps[0] + steps[1]
res[2] = max(steps[0] + steps[2],steps[1] + steps[2])
for i in range(3,n):
    print(f'res:{res}')
    res[i] = max(res[i-2]+steps[i], res[i-3]+steps[i-1]+steps[i])
print(f'steps:{steps} res:{res}')
print(res[n-1])

 

맨 처음에 내가 짯던 코드다

이상하게 계속 IndexError가 났다.

입력이 되는 만큼 리스트를 초기화 할 수 있도록 코드를 짯는데

무슨 이유인지는 모르겠는데 인덱스 에러가 난다.

 

그래서 구글링해서 다른 사람들의 코드를 찾아보니

처음부터 넉넉한 크기로 리스트를 초기화한다음에 거기에 숫자들을 대입하는 방식으로 했다.

이러니 통과가 되었다...;;

 

누구한테 이 문제를 물어볼 수 있을까...ㅠㅠ

n = int(input())

res = [0 for _ in range(301)]

steps = [0 for _ in range(301)]
for i in range(n):
    steps[i] = int(input())

res[1] = steps[0]
res[2] = steps[0] + steps[1]
res[3] = max(steps[0] + steps[2],steps[1] + steps[2])
for i in range(4,n+1):
    res[i] = max(res[i-2]+steps[i-1], res[i-3]+steps[i-1]+steps[i-2])

print(res[n])