#Algorithm
문제 번호
2579번 계단오르기(S3)
알고리즘 + 이론
DP이다.
정답 코드
# 2579번
# n <= 300 score <= 10000
# 계단을 올라갔을 때 최솟값을 저장
# 점수의 배열을 이용해 이 계단까지의 배열 최댓값 저장
# score[N] = score[N-2] + stair[N], score[N-3] + stair[N-1] + stair[N]
n = int(input())
stair = []
score = [0 for _ in range(n+1)]
for _ in range(n):
stair.append(int(input()))
cnt = 1
while 1:
if cnt == 1:
score[cnt] = stair[cnt-1]
elif cnt == 2:
score[cnt] = stair[cnt-2] + stair[cnt-1]
else:
score[cnt] = max(score[cnt-2]+stair[cnt-1], score[cnt-3]+stair[cnt-2]+stair[cnt-1])
if cnt == n:
break
cnt += 1
print(score[n])
느낀점 & 피드백
DP인걸 알고 풀었음에도 점화식을 생각하는 게 아직 어렵다.
손으로 먼저 써서 점화식을 구한 뒤 구현하는 게 맞는 순서인것 같다.
이 글이 도움이 되셨나요?