계단오르기-백준 파이썬

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

2579번: 계단 오르기

 

마지막계단을 밟아야 한다는게 핵심인것같다 이걸 동적계획법으로 구현한다면

이걸 동적계획법개념으로 적용시킨다면 내가밟은 타일이 i번째 타일일때

i최대값=i+max(i-1,i-2)

뭐이런식으로 하면 될것같다

# 계단오르기
d=[]
N=int(input())
for i in range(2):
    d.append(int(input()))
for i in range(2,N):
    d.append( int(input()) + max(d[-1],d[-2]) )
print(d)

이렇게 했는데 문제가 생겼다 

그렇다 연속으로 3계단을 밟으면 안된다는 룰을 어겼다

그부분을 어떻게 구현해야할까

 

10 20 15 25 10 20

10 10 10 10 10 10
   20 15 20 20 20
         25 25 25
            10 20

바로전계단을 밟았으면 1 그렇지않으면 0이라는 표시주었다

바로전계단이 1이면 전전계단과 현재 계단의 합을 구하고

0이면 전계단과 전전계단중 더큰것과 더한다

 

구현하니 일단 예제는 제대로 나오는것을 확인하였다

# 계단오르기
d=[]
N=int(input())
a=int(input())
d.append( [a, 0])
d.append( [a+int(input()), 1])
for i in range(2,N):
    if d[-1][1]==0:
        if d[-1][0]>d[-2][0]:
            d.append( [int(input())+d[-1][0],1] )
        else:
            d.append( [int(input())+d[-2][0],0] )
    else:
        d.append( [int(input())+d[-2][0],0] )

               
        
print(d)

첫번째 제출

# 계단오르기
import sys
input=sys.stdin.readline

d=[]
N=int(input())
a=int(input())
d.append( [a, 0])
d.append( [a+int(input()), 1])
for i in range(2,N):
    if d[-1][1]==0:
        if d[-1][0]>d[-2][0]:
            d.append( [int(input())+d[-1][0],1] )
        else:
            d.append( [int(input())+d[-2][0],0] )
    else:
        d.append( [int(input())+d[-2][0],0] )
print(d[-1][0])

틀렸다 이유가 뭘까

 

좀 미심쩍었던부분을 체크해본다 6개의 모든 계단이 10일때를 생각해보았지만 맞는 결과가 나왔다

 

이제 질문검색 코너로 가서 반례들을 찾아보기로 한다

 

반례발견했다

3 

1

2

100

일때 101이나온다 첫번째 계단을 건너뛸수있다는생각을 못했기때문에 발생한일 

# 계단오르기
# import sys
# input=sys.stdin.readline

d=[]
d2=[]
N=int(input())
a=int(input())
d.append( [a, 0])
d2.append( [a, 0])
b=int(input())
d.append( [a+b, 1])
d2.append( [b, 0])

for i in range(2,N):
    a=int(input())
    if d[-1][1]==0:
        if d[-1][0]>d[-2][0]:
            d.append( [a+d[-1][0],1] )
        else:
            d.append( [a+d[-2][0],0] )
    else:
        d.append( [a+d[-2][0],0] )
    
    if d2[-1][1]==0:
        if d2[-1][0]>d2[-2][0]:
            d2.append( [a+d2[-1][0],1] )
        else:
            d2.append( [a+d2[-2][0],0] )
    else:
        d2.append( [a+d2[-2][0],0] )

print(max(d[-1][0], d2[-1][0]))

위의 코드는 반례와

주어진코드가 잘작동했지만 틀렸습니다가 떳다

 

100 1000 1 4

인 계단이 있다고 쳐보자 

 

1까지는 첫번째를 스킵하고 두번째부터 시작하는게 최대였지만

4까지의 최대값은 100을 밟고 1000을밟은뒤 4를 밟는게 최대값이다

 

즉 이말은 2의 속성이 두가지가 필요하다는것이다 그리고 다른숫자에도 이 두가지 속성이 적용할 필요가 있다

 

생각해보니 3뿐만아니라 다른숫자도 한번건너뛰어서 온경우와 크게 건너뛰어서 온경우 모드를 표기하기로한다

멀 좋아할지몰라서 다준비했어처럼

 

제출

import sys
input=sys.stdin.readline
d=[]
N=int(input())
a=int(input())
d.append( [(a, 0),(a,1)])
b=int(input())
d.append( [(b, 0),(a+b,1)])
for i in range(2,N):
    c=int(input())
    d.append( [(c+max(d[-2][0][0], d[-2][1][0]),0 ), (c+d[-1][0][0],1 )] )
print(max(d[-1][0][0], d[-1][1][0]))

거의 100퍼찍는가 싶더니 value 에러가났다 

 

원인을 고민하다

N의 개수가 자연수인데 N이 1일경우 기본적으로 인풋을 하나 더받는다는걸 알아냈다 이게 오류의 원인일까?

 

제출

# 계단오르기
import sys
input=sys.stdin.readline

d=[]
N=int(input())


a=int(input())
d.append( [(a, 0),(a,1)])
if N>1:
    b=int(input())
    d.append( [(b, 0),(a+b,1)])

for i in range(2,N):
    c=int(input())
    d.append( [(c+max(d[-2][0][0], d[-2][1][0]),0 ), (c + d[-1][0][0], 1 )] )
        
# print(d)
print(max(d[-1][0][0], d[-1][1][0]))

정답!