💡 백준 2579: 계단 오르기
1️⃣ 3계단을 연속해서 밟을 수 없기 때문에 계단 i에 오를 때 i - 3, i - 1 계단을 밟거나 i - 2 계단을 밟을 수 있다. 마지막 도착 계단은 반드시 밟아야 하므로 i까지 계단마다
최적해를 구해 최댓값을 출력할 수 있다.
2️⃣ i - 3까지의 최적해 + i - 1 계단 자체의 점수(3계단을 연속해서 밟을 수 없으므로 바로 전 계단을 밟을 경우 전 계단의 직전 경로를 한 칸 띄워야 하며 그 칸의 최적해와 새 경로가 될 전 계단 값을 더해야 함, 직전 칸에 구해놓은 최적해는 어떤 경로로 온 것인지 알 수 없음)와 i - 2까지의 최적해(바로 전 계단을 밟지 않으므로 새 경로 계산이 필요 없음) 중 최댓값을 계단 i의 최적해로 한다.
🌱 코드 in Python
알고리즘: Dynamic Programing
import sys
h = int(sys.stdin.readline())
stair = [0] + [int(sys.stdin.readline()) for i in range(1, h + 1)]
if h < 2: # 주어진 계단의 수가 2보다 작을 경우 위와 같이 stair 배열을 할당할 경우 예외처리를 해주지 않으면 index error가 발생한다
print(stair[h])
else:
dp = [0] * (h + 1)
dp[1] = stair[1]
dp[2] = dp[1] + stair[2]
for i in range(3, h + 1):
dp[i] = max(dp[i - 2], dp[i - 3] + stair[i - 1]) + stair[i]
print(dp[h])이번 문제의 경우 점수의 최댓값을 찾는 문제이기 때문에 최적해를 찾는 방법인 DP 알고리즘을 사용하였다.
계단의 수가 2보다 작을 경우 최댓값은 0 또는 stair[1]이 된다
문제에서는 300이하의 자연수라고 되어있는데, 대부분의 백준 문제의 경우 명시되어 있지 않으면 자연수에 0을 포함하지 않는다고 하나 if h < 2 조건으로 0, 1을 동시에 처리할 수 있어 그렇게 처리하였다
계단 i를 오르는 방법은 1)i - 3, i - 1 계단 밟기 2) i - 2 계단 밟기 2가지가 있다
1)의 경우에 i - 3은 최적해를, i - 1은 계단 자체의 점수를 합산해야 한다
이는 i - 1의 최적해가 직전 계단을 밟았을 경우 3계단을 연속해서 밟게 될 수 있으므로, 그의 최적해는 무시하고 i - 3의 최적해 + i - 1의 점수를 더하여 새로운 경로로 최적해를 구해야 한다
2)의 경우에 i - 2를 밟을 경우 3계단이 연속해서 밟히지 않으므로 최적해를 더한다
🧨 이 문제의 가장 중요한 부분은 3계단을 연속해서 밟을 수 없다이기 때문에 구하려는 계단의 바로 직전과 그 전이 아닌, 3번째전과 2번째전이 기준이 되어야 한다는 것이다
🧠 기억하자
솔직히 저 중요한 부분을 잘 모르겠어서 한참 고민하다가 남의 코드 보고 해결했다 ^^..
오늘도 남의 창의력으로 뿌듯해지기 한 건 완료!
따흐흑..
그래도 일단은 배운걸 정리하자
-
지금은 문제를 보고 이거 DP로 풀 수 있다!를 파악하는 것부터 시작하는 것도 아니고, DP문제인 걸 알고 시작하는만큼 그 알고리즘으로 풀린다는 믿음을 좀 갖자! 3개가 연속으로 될 수 없을 때에는 직전 항이 아니라, 3번째전과 2번째전을 비교해야 한다. 이와 같은 류의 조건이 있을 경우
기준점을 어디에 둘 것인가를 항상 먼저 생각하자. -
문제를 좀 똑띠 읽자. 300이하의 자연수라는 조건이 있는데 왜! 더 생각을 안해서! 첫번째 시도에 index error를 맞았다. 정신 똑띠 차리자.
stair = [0] + [int(sys.stdin.readline()) for i in range(1, h + 1)]- 어제 알게된 배열 생성 방법을 응용해보았다. [0] + 와 같은 표현도 가능하다. 아니 파이썬 뭐지 진짜?
