[BOJ] 2579번: 계단 오르기 (DP)

 

(( 다시 풀기 !! ))

문제 링크

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

 

 

 

TIL

• DP문제는 보통 DP테이블을 무조건 배열로 정의 !!!!
  • dp[i] 를 i번째 계단까지 올라갔을 때 얻을 수 있는 최대 점수 라고 정의
• 점화식 필수 >> 이런 식으로 적당히 dp테이블과 그냥 score를 활용 !!
  • dp[i]는 두 가지 경우 중 최댓값을 취함 
  • i-2 번째 계단에서 i 번째 계단으로 이동하는 경우
    • dp[i] = dp[i-2] + score[i]
  • i-1 번째 계단에서 i 번째 계단으로 이동하는 경우 (단, i-1 번째를 밟았으므로 i-2 번째를 건너뛰어야 함)
    • dp[i] = dp[i-3] + score[i-1] + score[i]
• 순차적 DP 들어가기 전에 기본값 설정이 필요함 (초기 조건)
  • dp[1] = score[1]
  • dp[2] = score[1] + score[2]
  • dp[3] = max(score[1] + score[3], score[2] + score[3])
    (세 번째 계단을 오를 때 두 번째 계단을 밟거나 첫 번째 계단을 밟을 수 있음)
• 마지막 계단을 반드시 밟아야 한다는 조건이 어떻게 보장되는지 ?????
  • 항상 scores[i] (현재 계단 점수)를 포함하는 방식으로 dp[i]를 계산
    → 즉, 마지막 계단을 포함하지 않는 방법은 존재할 수 없음.
  • dp[i] = max(dp[i-2] + scores[i], dp[i-3] + scores[i-1] + scores[i])

 

[처음 코드 - 매우 틀림]

# 마지막 게단에서 시작
# 마지막 계단의 앞을 밟는 경우, 그 앞을 밟는 경우로 나눔
n = int(input())

stair = [int(input()) for _ in range(n)]

dp1 = stair[n-1] + stair[n-2]
dp2 = stair[n-1] + stair[n-3] 

if n==1:
    print(stair[0])

if n==2:
    print(stair[1]+stair[0])

else:
    cur = n-2
    is_third = True
    while cur > 0:
        if cur-2 >= 0:
            if stair[cur-1] > stair[cur-2]:
                if not is_third:
                    dp1 += stair[cur-1]
                    is_third = True
                    cur -= 1
                else:
                    dp1 += stair[cur-2]
                    is_third = False
                    cur -= 2
            elif stair[cur-1] < stair[cur-2]:
                dp1 += stair[cur-2]
                is_third = False
                cur -= 2
            else:
                if is_third:
                    dp1 += stair[cur-2]
                    is_third = False
                    cur -= 2
                else:
                    dp1 += stair[cur-1]
                    is_third = True
                    cur -= 1

        elif cur-1 >= 0 and not is_third:
            dp1 += stair[cur-1]
            is_third = True
            cur -= 1
        else: cur -= 1
        print(dp1)

    cur = n-3
    is_third = False
    while cur > 0:
        if cur-2 >= 0:
            if stair[cur-1] > stair[cur-2]:
                if not is_third:
                    dp2 += stair[cur-1]
                    is_third = True
                    cur -= 1
                else:
                    dp2 += stair[cur-2]
                    is_third = False
                    cur -= 2
            elif stair[cur-1] < stair[cur-2]:
                dp2 += stair[cur-2]
                is_third = False
                cur -= 2
            else:
                if is_third:
                    dp2 += stair[cur-2]
                    is_third = False
                    cur -= 2
                else:
                    dp2 += stair[cur-1]
                    is_third = True
                    cur -= 1

        elif cur-1 >= 0 and not is_third:
            dp2 += stair[cur-1]
            is_third = True
            cur -= 1
        else: cur -= 1
        print(dp2)

    print(max(dp1, dp2))

 

• 이 방법은 DP라기보단 Greedy에 가까워 최적의 해를 보장하지 않음
• is_third 변수를 사용하여 연속 3계단을 방지하려고 하고 있지만, 이 로직이 완벽하게 작동하지 않는 경우 존재
• 경우 나누는 방식 불완전
  • 현재 코드에서는 dp1과 dp2 두 가지 경로를 고려하지만,
    • stair[cur-1] > stair[cur-2]
    • stair[cur-1] < stair[cur-2]
    • stair[cur-1] == stair[cur-2]
  • 이러한 비교 조건만으로는 최적의 점수를 찾는 것이 어려움.
    왜냐하면, 특정 시점에서 최대 점수를 얻기 위해 거쳐야 하는 계단의 선택이 중요하기 때문

 

 

 

Code

def max_stair_score(n, scores):
    if n == 1:
        return scores[0]
    elif n == 2:
        return scores[0] + scores[1]
    
    dp = [0] * n
    dp[0] = scores[0]
    dp[1] = scores[0] + scores[1]
    dp[2] = max(scores[0] + scores[2], scores[1] + scores[2])

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

# 입력 처리
n = int(input())
scores = [int(input()) for _ in range(n)]

# 결과 출력
print(max_stair_score(n, scores))