[다이나믹 프로그래밍] ▲ 2579번 - 계단 오르기

[백준] 2579번 - 계단 오르기

(한줄평) 조건때문에 계속 헷갈려서 생각보다 어려웠던 문제! 코드는 단순하지만 복습이 필요하다!!

풀이 시간: 40분 이내

 

1) 문제 해결 아이디어

다음 조건을 만족하면서 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 문제다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

<i번째 계단을 선택했을 때 경우의 수>

i는 무조건 O이므로 (i - 1)은 O 혹은 X가 될 수 있다.

1. ~ OXOO일 때

- (i -1)이 O이면 (i -2)는 무조건 X여야한다. 조건2에서 연속된 세 개의 계단을 모두 밟아서는 안된다고 했기 떄문이다.

- (i-2)가 X이면 (i - 3)은 무조건 O여야 한다. 조건1에서 계단은 한 번에 오를 수 있는 계단 수는 2개가 최대라고 했기 때문이다.

그러므로 총 점수 =(i의 점수 + (i - 1)의 점수 + (i-3)을 선택했을 때 누적 점수)다.

2. ~ OXO일 때

- (i -1)이 X이면 (i -2)는 무조건 O여야한다. 조건1에서 계단은 한 번에 오를 수 있는 계단 수는 2개가 최대라고 했기 때문이다.

그러므로 총 점수 = (i의 점수 + (i-2)를 선택했을 때 누적 점수)다.

 

<점화식>

헷갈릴 때는 항상 d[i]는 항상 i를 선택했을 때의 최대, 최소값이라고 생각하고 점화식을 세우자!!

 

2) 소스코드

n = int(input())  # 계단의 개수(300이하 자연수)
graph = [int(input()) for _ in range(n)]  # n개의 계단 점수
d = [0] * 300
d[0], d[1] = graph[0], graph[0] + graph[1]
d[2] = graph[2] + max(graph[0], graph[1])
for i in range(3, n):
  d[i] = graph[i] + max(d[i - 3] + graph[i - 1], d[i - 2])
print(d[n - 1])

[참고] https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%802579%EB%B2%88%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EA%B3%84%EB%8B%A8-%EC%98%A4%EB%A5%B4%EA%B8%B0-DP

[백준] 2579번 계단오르기 파이썬 해설