DP 문제
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
(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) 일단 첫번째 조건을 읽는 순간 이 문제는 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를 짤 땐 재귀 점화식을 짤 때와 마찬가지로 무조건 !! 단순해질 수 밖에 없는 것 같다. 이상한 변수 도입하고 식이 복잡해지는 순간부터 내가 잘못짰다고 생각하면 될 것 같다 ..
*참고
[알고리즘] 백준 2579번 계단 오르기 python - Dynamic Programming
2579번: 계단 오르기
v3.leedo.me
https://daimhada.tistory.com/181
Python으로 푸는 백준 2579. 계단 오르기
백준 2579. 계단 오르기 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 계단에는 일정한 점수가 쓰여있으며 계단을 밟으면 그 계단에 쓰여있는 점수를 얻게 된다. 계단
daimhada.tistory.com