❓문제
❗문제 정리
📑코드
n=int(input())
stairs=[]
for i in range(n):
stairs.append(int(input()))
dp=[0]*301
if n==1:
print(stairs[0])
elif n==2:
print(sum(stairs))
else:
dp[0]=stairs[0]
dp[1]=dp[0]+stairs[1]
dp[2]=max(stairs[1]+stairs[2],dp[0]+stairs[2])
for i in range(3, n):#마지막칸 무조건 밟으니까 이전칸인 n-1까지만
dp[i]=max(dp[i-3]+stairs[i-1]+stairs[i],dp[i-2]+stairs[i])#dp[i-1] : 한칸 뛰어옴, dp[i-2]: 두칸 뛰어옴
print(dp[n-1])📝코드 설명
n=int(input())
stairs=[]
for i in range(n):
stairs.append(int(input()))
dp=[0]*301계단수 n, 계단 stairs 입력받기
dp테이블 만들어주기 - 최대 300개 이하의 계단이 있다고 하였으므로 dp테이블의 크기를 301로 설정.
여기서 dp테이블은 해당 인덱스번째까지 올라갔을때 점수의 최댓값!
if n==1:
print(stairs[0])
elif n==2:
print(sum(stairs))계단이 1개인경우 입력받은 계단에 올라가면 되므로 그대로 출력
계단이 2개인경우 최대 점수를 받으려면 있는 계단 2개를 모두 밝으면 된다. 전부 더해주기
- 92%에서 틀렸다고하면 이게 이유!!
else:
dp[0]=stairs[0]
dp[1]=dp[0]+stairs[1]
dp[2]=max(stairs[1]+stairs[2],dp[0]+stairs[2])
for i in range(3, n):#마지막칸 무조건 밟으니까 이전칸인 n-1까지만
dp[i]=max(dp[i-3]+stairs[i-1]+stairs[i],dp[i-2]+stairs[i])#dp[i-1] : 한칸 뛰어옴, dp[i-2]: 두칸 뛰어옴
print(dp[n-1])계단이 3개 이상인 경우 점화식 사용!!
💡내가 현재 계단에 서있는다고 생각하고 이전계단에서 어떻게 왔는지를 생각하기
1. 0번째 계단은 무조건 밟고 들어가기
2. 1번째 계단은 0번째 계단(이미 밟은 계단)의 점수에 현재 밟은 계단(1번째 계단)을 넣어주기
3. 2번째 계단은 1. 바로 다음 계단을 밟은다 2. 앞앞계단을 밟는다
3-1. 바로 다음 계단을 밟는 경우 : 이미 밟은 1번째 계단 + 현재 밟은 계단(2번째 계단)의 점수
3-2. 두칸 떨어진 계단을 밟는 경우 : 0번째 계단에서 2칸 떨어진 곳이 2번째 계단임.따라서, 0번째 계단의 점수와 현재 계단의 점수를 더함.
- 3번째 계단 부터는 점화식 사용
2번째 계단의 식을 확장해서 생각해보자.
dp[2]=max(stairs[1]+stairs[2],dp[0]+stairs[2])
dp[i]=max(stairs[i-1]+stairs[i],dp[i-2]+stairs[i])
(바로 다음 계단을 밟는 경우, 2칸 떨어진 계단을 밟는 경우)i=3이면, max(dp[0]+stairs[2]+stairs[3], dp[1]+stairs[3])
- 바로 다음 계단을 밟아서 세번째 계단에 온 경우, 3까지 오는데에서 한번은 두칸뛰어야함! 이전칸인 2번계단을 밟았으면,첫계단은 무조건 밟았으니 1번째 계단은 건너뛰었다.
3,2,0번째 계단을 밟아서 온 것! - 2칸 떨어진 계단을 밟아서 세번째 계단에 온 경우, 이전 계단인 2번째 계단을 건너뛰었으므로, 0,1,3계단으로 온 것이다.
🎖제출 결과
💡insight
반례 : https://www.acmicpc.net/board/view/102597
헷갈렸던게, 최소로 이동해서 최댓값을 내는거라고 착각함!!!
AI dev