[백준] 2579번 - 계단 오르기 (파이썬)

 

 

백준 2579번 계단 오르기 파이썬

 

2579번: 계단 오르기

 

2579번

 

해당 2579번 문제는 300개 이하의 계단이 주어지며 각 계단마다 다른 점수를 흭득할 수 있다.

 

 

 

이러한 상황 가운데서 위와 같은 조건에 맞춰 얻을 수 있는 점수의 최댓값을 흭득하는 문제다.

 

 

" 💡 문제 해결 아이디어 "

 

해당 문제는 특정 위치에서의 최댓값을 구하는 문제이므로 조건을 잘 세워야한다.

 

본인은 이번 문제에서 dp테이블의 값의 기준을 다음과 같이 정의하여 해결하였다.

 

dp[i] : i번째 계단에서 흭득할 수 있는 최댓값

 

또한 다음과 같은 경우를 고려해야한다.

 

가능한 이동 경우: 계단을 한칸 오르는 경우, 계단을 두칸 오르는 경우

필수 조건: 마지막 계단은 밟아야 함.

두 조건을 결합하면 값을 계산할 수 있는 두 가지 경우를 도출할 수 있다.

 

만약 1 2 3 4의 계단이 있다면

"1,3,4"(dp[i-3]+step[i-1]+step[i]) 를 고려한 경우 / "1,2,4"(dp[i-2]+step[i]) 를 고려한 경우 (마지막 계단은 밟아야하므로 무조건 마지막은 밟는 경우 내에서 최댓값 찾기)

 

다음과 같은 아이디어를 통해 코드를 구현하면 아래와 같다.

 

 

 

코드

# 가능한 이동 경우:
# 계단을 한칸 오르는 경우, 계단을 두칸 오르는 경우

# 필수 조건:
# 마지막 계단은 밟아야 함.

# 두 조건을 합쳐 생성한 조건:
# 1 2 3 4의 계단이 있다면 "1,3,4"를 고려한 경우 / "1,2,4"를 고려한 경우 (마지막 계단은 밟아야하므로 무조건 마지막은 밟는 경우 내에서 최댓값 찾기)


n = int(input())
step = [0 for _ in range(301)] # 계단은 300이하의 숫자이므로 301개의 인덱스 생성
for i in range(1,n+1):
    step[i] = int(input())

dp = [0 for _ in range(301)] # dp[i] : i번째 계단에서 흭득할 수 있는 최댓값

# 기본값 주입
dp[1] = step[1]
dp[2] = step[1] + step[2]
dp[3] = max(step[1]+step[3], step[2]+step[3])
for i in range(4,n+1):
    dp[i] = max(dp[i-3]+step[i]+step[i-1], dp[i-2]+step[i])

print(dp[n])