[백준] 2579번 문제 풀이 : 파이썬(python) 코드 설명

www.acmicpc.net/problem/2579

2579번: 계단 오르기

---

Hint

 

Dynamic Programming은 어떠한 규칙이 있다

해당 규칙을 이용하면 쉽게 답을 작성할 수 있다

 

필자는 list in list 형식을 이용함

 

---

Solution

T=int(input())
L=[]
for i in range(T):
    L.append(int(input()))
if T==1:
    print(L[0])
else:
    L[0]=[L[0],L[0]]
    L[1]=[L[0][0]+L[1],L[1]]

    for i in range(2, T):
        L[i]=[L[i]+L[i-1][1], L[i]+max(L[i-2])]

    print(max(L[T-1]))

해당 코드의 매커니즘을

2579번 예시와 함께 소개해보겠습니다.

 

 

index 0과 1은 점화식에 맞지 않기 때문에

미리 계산을 해줍니다

 

L[i]의 구성은 위처럼

[i-1번째 계단을 밟았을 때 최댓값, i-2번째 계단을 밟았을 때 최댓값]

으로 되어있습니다.

 

먼저 i-1번째 계단을 밟았을 때 최댓값은

i-1번째 계단이 i-2번째 계단을 밟으며 안되므로(문제 조건)

i-1번째(j번째) 계단 기준 i-3(j-2)번째 계단을 밟았을 때 최댓값을

더해주어야 합니다

 

 

즉, L[i][0] = L[i]+L[i-1][1] 임을 알 수 있죠

 

 

(L[i-1][0]은 이미 i-1계단이 i-2계단을 밟은 경우이므로 문제 조건에 어긋남)

 

 

두 번째로 L[i][1]입니다.

L[i][1]은 i-2번째 계단을 밟은 최댓값입니다.

이 경우 i-2번째 계단이 i-3을 밟든 그 전에 있는 계단을 밟든

상관이 없는 경우입니다.

그러므로 L[i-2] 리스트 내에 있는 값 중 최댓값을 더하면 됩니다.

 

즉, L[i][1] = L[i]+max(L[i-2])임을 알 수 있습니다

 

 

결론적으로 점화식을 세우면

i >= 2일 때

L[i] = [L[i]+L[i-1][0], L[i]+max(L[i-2])]

로 코드를 작성할 수 있습니다

 

 

추가 예시

Index	0	1	2	3	4	5
Value	10	20	30	40	150	30
L[i]	[10, 10]	[30, 20]	[50, 40]	[80, 70]	[220, 200]	[230, 110]

L[2]=[30+20, 30+10]

L[3]=[40+40, 40+30]

L[4]=[150+70, 150+50]

L[5]=[30+200, 30+80]