백준 2579번 문제(계단 오르기) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

2579번: 계단 오르기

 

정답 코드는 아래와 같습니다.

import sys
 
def solve():
  n = int(sys.stdin.readline().rstrip())
  arr = [0]
  for _ in range(n):
    x = int(sys.stdin.readline().rstrip())
    arr.append(x)
  g = [0, 0]
  h = [0, arr[1]]
  for i in range(2, n+1):
    g.append(h[i-1] + arr[i])
    h.append(max(h[i-2], g[i-2]) + arr[i])
  print(max(g[n], h[n]))
 
solve()
 

 

주어진 예시를 이용하여 실제 정답을 구해보고, 그 과정에서 중복된(비효율적인) 부분을 찾고,

이것을 더 효율적으로 계산할 수 있는 방법을 떠올립니다.

 

이번 문제도 실제로 해보면 결국,

현재(x번째)의 계단에 오르기 위해서는 그 전(x-1번째) 계단에서 오르거나, 그 전전(x-2번째) 계단에서 올라야 하는데,

그 전전(x-2번째) 계단에서 오를 때에는 제약이 없지만, 그 전(x-1번째) 계단에서 오를 때에는 제약(x-1번째 오를 때 x-2번째로부터 오르지 않은 경우만 오를 수 있음)이 있습니다.

따라서 각 계단에서 제약이 있는 경우(list g)와 없는 경우(list h)에 대한 정답을 모두 저장하고, 이 값을 모두 채워나가는 방식으로 풀어낼 수 있습니다.(RGB 거리 문제와 유사)

제약이 있다는 말은 즉 이전에 한 칸을 올랐다는 것이고(그러니까 그 다음에는 두 칸을 오르지 못한다는 것)

제약이 없다는 말은 즉 이전에 두 칸을 올랐다는 것입니다.(index 2의 경우는 예외)

 

728x90

 

소스코드에서

g 값을 update 할 때에는 그 이전에 두 칸 오른 값에다가 현재의 값을 더해주면 될 것이고(한 칸을 오르기 위해서는 그 이전에는 반드시 두 칸을 올랐어야 하기 때문에)

h 값을 update 할 때에는 그 전전에 값들 중에서 더 큰 값에다가 현재의 값을 더해줍니다.(어차피 두 칸을 올라서 현재 위치에 도착하는 것이므로, 전전에 어떻게 올랐었는지 상관이 없기 때문)

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=1ehx6uoFZkU 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)