백준(baekjoon) 2579번: 계단 오르기(실버 3, 파이썬 PYTHON) - 동적 계획법 1

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

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

2579번: 계단 오르기

 

import sys

n=int(sys.stdin.readline())
score=[]
result=[0]*n

for _ in range(n):
  save=int(sys.stdin.readline())
  score.append(save)

for x in range(n):
  if(x==0):
    result[0]=score[0]
  elif(x==1):
    result[1]=score[0]+score[1]
  elif(x==2):
    result[2]=max(score[2]+score[1],score[2]+score[0])
  else:
    result[x]=max(score[x]+score[x-1]+result[x-3],score[x]+result[x-2])

print(result[n-1])

 

※ 동적 계획법 1

 

 

● 계단의 수를 n에 입력받고, 점수를 저장할 빈 배열 score, 각 계단에서의 점수를 저장할 값이 0으로 초기화 되어있는 n 크기의 배열 result를 정의해준다. 그 후의 입력들을 score에 차례대로 append 해준다.

 

● x는 0부터 n-1 까지 돈다.

case 1: x가 0일 때-> 첫 계단까지 점수의 최대합은 첫 계단 점수의 값이므로 result[0] 에 score[0] 의 값을 넣어준다.

 

case 1: x가 1일 때

-> 두번째 계단까지 점수의 최대합은 첫 계단과 두번째 계단 점수의 합이므로 result[1] 에 score[0]+score[1] 의 값을 넣어준다.

 

case 2: x가 2일 때

-> 세번째 계단까지 점수의 최대합은 첫번째 계단과 세번째 계단의 점수 합과 두번째 계단과 세번째 계단의 점수 합 중 더 큰 값이므로 result[2]에 max(score[0]+score[2], score[1]+score[2]) 의 값을 넣어준다.

 

case 3: x가 3 이상일 때

->

x+1번째 계단까지 점수의 최대합은 x+1번째 계단의 점수와 x번째 계단의 점수와 x-2번째 계단까지 점수를 계산한 최대값을 모두 합한 값과, x+1번째 계단의 점수와 x-1번째 계단까지 점수를 계산한 최대 값을 더한 값 중 더 큰 값이므로, result[x] 에 max(score[x]+score[x-1]+result[x-3],score[x]+result[x-2]) 값을 넣어준다.

 

● result[n-1] 의 값을 출력해주면 답을 구할 수 있다!

 

 

결과