백준 2579 문제 풀이 python

🐒 계단 오르기

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

✍ 나의 풀이

import sys

n = int(input())

stair = [0] * 301

for i in range(1,n+1):
    stair[i] = int(sys.stdin.readline().rstrip())

dp = [0] * 301

dp[1] = stair[1]
dp[2] = dp[1] + stair[2]

for i in range(3,n+1):
    dp[i] = max(dp[i-3]+stair[i-1]+stair[i], dp[i-2]+stair[i])

print(dp[n])

첫트에 못풀고 다른 사람들의 풀이를 보고나서
다른 날에 다시 풀어보았다.

🧠 문제 이해

규칙을 찾는게 중요한 것 같다.

문제에서는 계단을 한칸 또는 두칸씩 올라갈 수 있지만
세칸을 연속으로 올라갈 수 없다고 한다.
또한 마지막 계단은 꼭 밟아야한다.

계단을 올라서 얻을 수 있는 점수의 최대값을 출력해야한다.

접근을 잘못하면 최대 점수를 얻기위해 세칸씩 연속해서 계단을 오르는 문제가 생긴다.

문제를 풀기 위해선 계단에 올라온 후의 관점에서 어떻게 올라왔는지 생각해야한다고 어떤 블로그에서 설명했다.

예를 들어 네칸의 계단이 있다고 했을때 계단을 오르는 방법은 세가지이다.

2번 방법은 계단을 두개씩 건너밟았다. 1번 방법보다 한칸 덜 밟았다.
때문에 1번 방법보다 점수가 낮게 나온다. 최대 점수를 구하고 있으므로 2번 방법은 제외한다.

현재 위치가 4번째 계단일때,

두칸 전 계단까지의 최대 점수의 합 + 현재 계단의 점수
vs
세칸 전 계단까지의 최대 점수의 합 + 한칸 전 계단의 점수 + 현재 계단의 점수

둘 중 값이 높은 쪽이 현재 계단까지의 최대 점수가 된다.

이 두가지 방법을 비교해서 점수가 큰쪽을 선택하기를 반복하면 최대 점수를 얻을 수 있다.

여기서
세칸 전 계단까지의 최대 점수의 합 + 두칸 전 계단의 점수 + 현재 계단의 점수
vs
세칸 전 계단까지의 최대 점수의 합 + 한칸 전 계단의 점수 + 현재 계단의 점수
로 비교를 해버리면 문제에서 제시된 예제를 입력했을때 세번 연속해서 계단을 밟는 경우가 발생한다.

코드설명

먼저 모든 계단의 점수를 stair 리스트에 저장한다.

import sys

n = int(input())

stair = [0] * 301
#각 계단의 점수를 저장할 수 있는 리스트를 만든다
 # 계단은 최대 300개까지 나올 수 있다고 명시되어있기에 하드코딩했다.

for i in range(1,n+1):
    stair[i] = int(sys.stdin.readline().rstrip())
    	#한줄씩 계단의 점수가 입력되기에 1번계단부터 n번계단까지 반복해서 입력받는다.
         # 반복문 안에서 입력받으므로 input이 아닌 readline을 사용했다.

계단의 점수를 저장했으니 dp테이블에 현재 계단까지 올라오면서 얻은 최대점수의 합을 저장한다.

dp = [0] * 301
#각 계단까지 올라왔을때의 최대 점수를 저장하는 리스트를 만든다.
 # 계단의 갯수와 동일한 크기로 만든다.

dp[1] = stair[1] 	#계단이 하나일 경우, 첫번째 계단을 올라 얻는 점수가 최대점수이다.
dp[2] = dp[1] + stair[2]	#계단이 두개일 경우, 첫번째,두번째 계단을 올라 얻는 점수가 최대 점수이다.

for i in range(3,n+1):
    dp[i] = max(dp[i-3]+stair[i-1]+stair[i], dp[i-2]+stair[i])
 #max 함수를 통해  세칸 전 계단까지의 최대 점수의 합 + 한칸 전 계단의 점수 + 현재 계단의 점수 
 #					두칸 전 까지의 최대 점수의 합 + 현재 계단의 점수  둘 중 최대 값을 현재 계단까지의 최대 점수로 저장한다.

print(dp[n])

🔍 다른 답안

계단 갯수를 하드코딩 하기 싫다면 if문을 통해 다르게 코드를 짤 수 있다.

import sys

n = int(input())

stair = [0] * (n+1)

for i in range(1,n+1):
    stair[i] = int(sys.stdin.readline().rstrip())

dp = [0] * (n+1)

if n == 1:
    print(stair[1])
elif n == 2:
    print(stair[1] + stair[2])
else:
    dp[1] = stair[1]
    dp[2] = dp[1] + stair[2]

    for i in range(3,n+1):
        dp[i] = max(dp[i-3]+stair[i-1]+stair[i], dp[i-2]+stair[i])

    print(dp[n])