시행착오
예제에 갇히지 말자
- 계단 오르기 문제랑 비슷해서 분명 똑같을 리가 없는데.. 하며 문제를 계속 다시 읽고 DP를 다 출력해보니까 무조건 마지막이 max가 아니더라.
- 그래서 처음에 단순히 print(max(DP))로 작성.. 예제는 맞겠지만 당연히 다른 문제에는 틀렸을 것이다.
전체 코드를 다 보자
- 예제의 경우를 보자. 마지막까지 마신 32보다 마지막은 안 마신 33이 더 크다. 이 말을 i번째 잔을 고려할 때 마시지 않아도 된다는 뜻이다. 계단 문제와 다르게 마지막을 꼭 마셔야 되는 것이 아니니까!
- 그래서 DP에 append할 때 wine[i-1]+DP[i-3]와 DP[i-2] 크기 비교뿐만 아니라 DP[i-1]도 비교해주어야 한다.
- 그치만 또 바보같이... for문에서만 고치고 DP[2]일 때는 적용시켜주지 않았다.... 꼭꼭 하나에만 매몰되지 말자
런타임 에러
- 해결된 줄 알았는데 웬 런타임 에러 ㅎㅎㅎㅎ
- 코드를 열심히 째려보니.. n은 1부터 가능한데, 3 이상일 때만 고려해서 적어놨더라. 즉, n이 1이나 2일 때 접근 불가능한 곳으로 접근하게 되는 것이다.
for문은 n이 3보다 작으면 실행되지 않기에 문제가 없다.
코드
import sys
input = sys.stdin.readline
n = int(input())
wine = []
for _ in range(n):
wine.append(int(input()))
DP = [wine[0]]
if n > 1:
DP.append(wine[0]+wine[1])
if n > 2:
DP.append(max(wine[0]+wine[2], wine[1]+wine[2], DP[1]))
for i in range(3, n):
DP.append(max(wine[i-1]+DP[i-3]+ wine[i], DP[i-2]+ wine[i], DP[i-1]))
print(DP[n-1])
결과
- 문제를 너무 가볍게 풀고 있는 것 같다.. 코테 현장이라고 생각하고 문제 하나하나 깊게 보고 모든 걸 고려해서 신중히 짜자
