[백준 2579 계단오르기 python, java]

문제 링크

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

2579번: 계단 오르기

문제

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

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

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

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

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

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

 

아이디어

 

 

 

문제 조건

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

1번과 2번 조건을 반영하기 위해서

현재 계단을 밟고 있다면, 내가 전 계단을 밟았는지 밟지 않았는지를 알아야한다.

-> 상태를 관리해야하는 dp 문제

 

 

 

가능한 상태의 종류

현재 계단을 밟고있고, 이전 계단도 밟았음

현재 계단을 밟고있고, 이전 계단은 밟지 않았음

현재 계단을 밟지 않고있고, 이전 계단은 밟았음

현재 계단을 밟지 않고있고, 이전 계단도 밟지 않았음 → 1번 조건에 의해서 불가

 

 

따라서

 

현재 보고있는 계단이 몇번째 계단인지

현재 계단을 밟는지,

이전 계단을 밟았는지를

저장하며 갱신해야한다.

 

 

3차원 dp 배열 활용

dp[인덱스][현재 계단을 밟을지][이전 계단을 밟았는지]

 

dp[2][0][1] : 현재 보고있는 2번째 계단을 밟지 않고 이전 계단인 1번째 계단을 밟았을 때의 최댓값

dp[2][1][0] : 현재 보고있는 2번째 계단을 밟고 이전 계단인 1번째 계단을 밟지 않았을 때의 최댓값

 

 

 

주석 포함 코드

 

n = int(input())
dp = [[[0 for _ in range(2)] for _ in range(2)] for _ in range(n)]
arr = [0] * n
for i in range(0,n):
    arr[i] = int(input())

if n == 1:
    print(arr[0])
else:
		# dp[i][j][k]
		# i: 계단index
		# j: 현재 계단인 i 계단을 밟는가?
		# k: 이전 계단인 i-1 계단을 밟았는가?

    dp[0][0][1] = 0      # 0번째 계단을 안밟았고 (이전 계단은 밟았다.)
    dp[0][1][0] = arr[0] # 0번째 계단을 밟았고 (이전 계단은 안밟았다.)
    dp[0][1][1] = arr[0] # 0번째 계단을 밟았고 (이전 계단도 밟았다.)

    dp[1][0][1] = dp[0][1][0]           # 1번째 계단을 안밟았고 0번째 계단은 밟았다.
    dp[1][1][0] = arr[1]                # 1번째 계단을 밟았고 0번째 계단은 안밟았다.
    dp[1][1][1] = dp[0][1][0] + arr[1]  # 1번째 계단을 밟았고 0번째 계단도 밟았다.

    for index in range(2, n):

				# 현재 계단을 안밟고 이전 계단은 밟은 경우
				# 말 그대로 이전 계단을 밟은 경우 중 최댓값으로 갱신
        dp[index][0][1] = max(dp[index - 1][1][0], dp[index - 1][1][1])

				# 현재 계단을 밟고 이전 계단은 안밟은 경우
				# 이전 계단을 안밟으므로 2계단 전의 계단은 밟았어야 한다.
				# 2계단전의 최대 점수와 현재 계단 점수 합산
        dp[index][1][0] = max(dp[index - 2][1][0], dp[index - 2][1][1]) + arr[index]

				# 현재 계단을 밟고 이전계단도 밟은 경우
				# 예를 들어 현재 5번째 계단이라면, 5번째도 밟을거고, 4번째도 이미 밟고 온 경우이다.
				# 이 때는 3번째 계단을 밟은 경우를 빼줘야함
        dp[index][1][1] = dp[index - 1][1][0] + arr[index]

		# 문제 조건에서 마지막 (n-1번째) 계단을 꼭 밟아야 하므로
		# 마지막  계단을 밟은 경우들 중 최댓값이 정답
    print(max(dp[n - 1][1][0], dp[n - 1][1][1]))

 

주석 없는 코드

 

n = int(input())
dp = [[[0 for _ in range(2)] for _ in range(2)] for _ in range(n)]
arr = [0] * n
for i in range(0,n):
    arr[i] = int(input())

if n == 1:
    print(arr[0])
else:
    dp[0][0][1] = 0
    dp[0][1][0] = arr[0]
    dp[0][1][1] = arr[0]

    dp[1][0][1] = dp[0][1][0]
    dp[1][1][0] = arr[1]
    dp[1][1][1] = dp[0][1][0] + arr[1]

    for index in range(2, n):
        dp[index][0][1] = max(dp[index - 1][1][0], dp[index - 1][1][1])
        dp[index][1][0] = max(dp[index - 2][1][0], dp[index - 2][1][1]) + arr[index]
        dp[index][1][1] = dp[index - 1][1][0] + arr[index]

    print(max(dp[n - 1][1][0], dp[n - 1][1][1]))