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

DP 문제

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

2579번: 계단 오르기

 

(1) 처음에 내가 생각한 방식 (실패)

# 계단오르기 (실버3)
import sys
n = int(sys.stdin.readline())
score = []
for _ in range(n):
    i = int(sys.stdin.readline())
    score.append(i)

def ans(score):
    dp = [0] * n
    dp[n -1] = score[n - 1] 
    dp[n - 2] = score[n -1] + score[n - 2] # 연속해서 두개
    dp[n - 3] = score[n -1] + score[n - 3]
    cnt = 0
    for i in range(n - 4, -1, -1):
        maxNum = max(dp[i + 1], dp[i + 2])
        if i == n - 4: maxNum = dp[i + 1]
        if maxNum == dp[i + 1] :
            cnt += 1
            if cnt >= 2:
                cnt = 0
                maxNum = dp[i + 2]
        # print(maxNum, end=' ')
        dp[i] = max(dp[i], maxNum+ score[i])
    print(dp)
    print(dp[0])
    maxTmp = dp[0]
    cnt = 0
    for i in range(n - 4, -1, -1):
        maxNum = max(dp[i + 1], dp[i + 2])
        if i == n - 4: maxNum = dp[i + 2]
        if maxNum == dp[i + 1] :
            cnt += 1
            if cnt >= 2:
                cnt = 0
                maxNum = dp[i + 2]
        dp[i] = max(dp[i], maxNum+ score[i])
    print(dp)
# print(dp[0])
    maxTmp = max(maxTmp, dp[0])
    print(maxTmp)

if n == 1: print(score[0])
elif n == 2: print(score[1] + score[0])
elif n == 3: print(max((score[0] + score[2]), (score[1] + score[2])))
else: 
    ans(score)

 

지금 보니까 정말 정답만 맞추려고 쓰레기처럼 짠 것 같다 .. 일단 n이 1이나 2일 때 배열의 index 범위를 벗어날 시 에러가 안나도록 예외처리를 해주었는데 이부분도 충분히 개선할 수 있었지만 일단 생각나는대로 짰다. 

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

1) 일단 첫번째 조건을 읽는 순간 이 문제는 dp로 풀어야겠다고 생각하고 dp로 짰다.

2) 두번째 조건 때문에 좀 까다로워졌는데, 이 때문에 cnt라는 변수를 도입하고 이 cnt가 2 이상 되면 바로 직전 계단을 밟는게 최댓값이더라도 강제로 전전 계단을 밟도록 만들어주었다.

3) 세번째 조건으로 인해, 마지막 계단은 꼭 포함하도록 for문에 진입하기 전에 미리 dp 배열에 값을 입력해두었다.

4) 기타 코드 : if i == n - 4: maxNum = dp[i + 1] 이 코드는 왜 넣었냐면 처음 시작할 때 직전 계단 / 전전 계단을 밟는 케이스 모두 고려하여 마지막에 최댓값을 도출하도록 하기 위함에서이다. (이러한 예외처리를 해주었을 때부터 내 dp 점화식이 잘못됐다는 걸 깨달음 ..)

ex)

12
0
1
1
100
100
1
1
1
1
1
100
100
=> [204, 204, 204, 203, 203, 103, 103, 102, 102, 101, 200, 100]
204
=> [403, 403, 303, 402, 302, 203, 202, 102, 201, 101, 200, 100]
403

(2) 처음에 내가 생각한 방식이 틀린 이유 

이렇게 코드를 짰을 시 대부분의 반례는 모두 맞았지만, 다음과 같은 경우에는 올바르지 못한 답을 도출했다. 

ex)

10
100
100
1
1
100
100
1
1000
1000
1000
[2301, 2301, 2201, 2101, 2200, 2100, 2001, 2000, 2000, 1000]
2301
[2301, 2301, 2201, 2101, 2200, 2100, 2001, 2000, 2000, 1000]
2301

 

정답 : [2302, 2301, 1302, 302, 301, 301, 201, 101, 200, 100, 0]

 

보기 좋게 바꾸어 내 답과 정답 dp를 비교해보았다.

내 dp : [100, 200, 101, 201, 301, 301, 302, 1301, 2301, 2301]

정답 dp : [100, 200, 101, 201, 301, 301, 302, 1302, 2301, 2302]

 

dp 배열을 모두 출력해서 값을 비교해보았음에도 왜 대체 위의 코드가 잘못된건지 모르겠어서 그림을 그려서 확인해보았다.

 

파란색은 직전 계단에서의 값을, 핑크색은 전전 계단에서의 값을 가져왔음을 나타낸다.

문제는 위의 사진의 노란색 형광펜을 칠한부분처럼 직전 계단에서의 값과 전전 계단에서의 값이 같을 때 나타난다. 여기서 마지막 계단에서 최댓값을 얻으려면 바로 저기에서 전전 계단에서 값을 들고 와야한다. 하지만, 위의 내 코드에선 cnt가 2가 넘지 않고, 직전/전전 계단에서의 값이 같을 시에는 직전 계단에서 값을 들고 왔기 때문에 문제가 생겼던 것 같다. 또, max값을 들고 오는 과정에서 cnt라는 변수와 얽혀 cnt가 2이상일 땐 무조건 전전 계단에서 값을 가져오도록 한게 문제발생 이유였던 것 같다.

 

(3) 수정 후 내 코드 (성공)

 

1) cnt를 도입해서 연속해서 두계단 이상 못가도록 한 것을 dp 배열과 score 배열을 적절하게 잘 사용하여 조건을 만족할 수 있게 수정하였다.

2) 나는 마지막 계단을 무조건 밟아야한다길래 for문을 반대로 돌며 배열 값을 거꾸로 채워나갔는데 그럴 필요가 없었다. 어차피 dp의 마지막 값을 구하면 그 값에는 마지막 계단의 값이 무조건 포함되기 때문이다.

# 계단오르기 (실버3)
import sys
n = int(sys.stdin.readline())
score = []
for _ in range(n):
    i = int(sys.stdin.readline())
    score.append(i)

def ans(score):
    dp = [0] * n
    dp[0] = score[0]
    dp[1] = score[0] + score[1] # 연속해서 두개
    dp[2] = max(score[0] + score[2], score[1] + score[2])
    for i in range(3, n):
        dp[i] = max(dp[i-3] + score[i-1] + score[i], dp[i-2] + score[i])
    # print(dp)
    print(dp[n-1])

if n == 1: print(score[0])
elif n == 2: print(score[1] + score[0])
elif n == 3: print(max((score[0] + score[2]), (score[1] + score[2])))
else: 
    ans(score)

 

해당 계단을 밟을 때마다 max(직전계단을 밟을 시, 전전계단을 밟을 시)의 최댓값을 도출했다. 어차피 두계단밖에 연속적으로 갈 수 없으므로 매 계단을 밟을 때마다 선택지는 두가지밖에 없다. 

 

느낀점 : dp를 짤 땐 재귀 점화식을 짤 때와 마찬가지로 무조건 !! 단순해질 수 밖에 없는 것 같다. 이상한 변수 도입하고 식이 복잡해지는 순간부터 내가 잘못짰다고 생각하면 될 것 같다 ..

 

*참고

https://v3.leedo.me/devs/64

[알고리즘] 백준 2579번 계단 오르기 python - Dynamic Programming

https://daimhada.tistory.com/181

Python으로 푸는 백준 2579. 계단 오르기