BOJ(백준) 2579[계단 오르기]

이 문제는 주어진 계단을 오를 때 얻을 수 있는 최대 점수를 구하는 문제입니다. 계단은 특정 규칙에 따라 올라야 하며, 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다. 문제를 분석하고 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

1. 문제 설명

백준 2579번 문제 “계단 오르기”는 주어진 계단을 오르면서 얻을 수 있는 최대 점수를 구하는 문제입니다. 계단을 오를 때 다음 규칙을 따라야 합니다:

 

1) 계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있습니다.

2) 연속된 세 개의 계단을 모두 밟아서는 안 됩니다.

3) 마지막 계단은 반드시 밟아야 합니다.

 

2. 문제 접근법

이 문제를 해결하기 위해 동적 계획법을 사용합니다. 핵심 아이디어는 각 계단에 도달할 때까지 얻을 수 있는 최대 점수를 미리 계산하고 저장하여, 그 값을 사용해 더 큰 수의 최대 점수를 쉽게 구하는 것입니다. 접근 방법은 다음과 같습니다:

 

1) 초기값 설정

• 첫 번째 계단의 점수는 d[0]에 저장합니다.
• 두 번째 계단의 점수는 첫 번째 계단의 점수와 두 번째 계단의 점수를 더한 값입니다.
• 세 번째 계단의 점수는 첫 번째 계단과 세 번째 계단을 밟는 경우와 두 번째 계단과 세 번째 계단을 밟는 경우 중 큰 값입니다.

 

2) DP 배열 사용

최대 점수를 저장할 배열 d를 만듭니다. 여기서 d[i]는 i번째 계단까지 오를 때 얻을 수 있는 최대 점수를 저장합니다.

 

3) 반복적 계산

4번째 계단부터는 다음과 같은 점화식을 사용합니다:

• d[i] = max(stair[i] + stair[i-1] + d[i-3], stair[i] + d[i-2])

이는 i번째 계단을 밟을 때, i-1번째 계단도 밟는 경우와 i-2번째 계단을 밟는 경우 중 더 큰 값을 선택하여 계산합니다.

 

4) 최적해 도출

최종적으로 d[N-1]이 우리가 찾는 답이 됩니다.

3. 정답 코드

import sys
input = sys.stdin.readline

N = int(input())    # 계단의 수 입력
stair = [0] * N     # 계단 점수를 저장할 리스트 초기화
for i in range(N):
    stair[i] = int(input())  # 각 계단의 점수 입력

d = [0] * N  # 최대 점수를 저장할 리스트 초기화
for i in range(N):
    if i == 0:
        d[i] = stair[i]                 # 첫 번째 계단의 점수
    elif i == 1:
        d[i] = stair[i] + stair[i-1]    # 두 번째 계단의 점수
    elif i == 2:
        d[i] = max(stair[i] + stair[i-1], stair[i] + stair[i-2])  # 세 번째 계단 점수 계산
    else:
        # 점화식을 이용하여 계산
        # 1) 연속된 계단 밟는 경우 2) 마지막 계단에서 두칸떨어진 계단 밟는 경우
        d[i] = max(stair[i] + stair[i-1] + d[i-3], stair[i] + d[i-2])

print(d[N-1])  # 마지막 계단에서의 최대 점수를 출력

 

4. 코드 설명

 

위 코드는 주어진 계단을 오를 때 얻을 수 있는 최대 점수를 동적 계획법을 사용하여 계산합니다. d 배열은 각 계단에 대해 최대 점수를 저장하며, 반복문을 통해 규칙을 따르며 점수를 계산합니다.

 

1. 첫 번째 계단의 점수는 d[0]에 저장됩니다.
2. 두 번째 계단의 점수는 첫 번째 계단의 점수와 두 번째 계단의 점수를 더한 값으로 저장됩니다.
3. 세 번째 계단의 점수는 첫 번째 계단과 세 번째 계단을 밟는 경우와 두 번째 계단과 세 번째 계단을 밟는 경우 중 큰 값으로 저장됩니다.
4. 네 번째 계단부터는 i번째 계단을 밟을 때, i-1번째 계단도 밟는 경우와 i-2번째 계단을 밟는 경우 중 더 큰 값을 선택하여 점수를 계산합니다.

최종적으로 마지막 계단에서의 최대 점수 d[N-1]을 출력하게 됩니다.

5. Github으로 확인

coTest/BOJ/BOJ01_10_03_2579.py at main · pcy4196/coTest