[BOJ] 2579번 - 계단오르기

요즘 부족한 유형(dp, 백트래킹, 구현 등) 위주로 공부를 하고 있다.

물론 맨날 부족한 부분만 하는건 아니고 재밌어 보이는 문제를 풀 때도 있다. 문제가 잘 안 풀리는 것들은 고민 좀 하다가 다른 문제를 푼다.

답지를 봐 버리면 뭔가 스스로 좀 그래서,,, (진짜 안 될 때는 보기도 한다. ㅋ.ㅋ)

 

이번에는 저번에 풀어보려다가 풀지 못했던 DP문제를 오늘 드디어 해결했다. 자꾸 1차원 배열로 하려고 했던 생각을 고치고 2차원 배열을

만든 다음 해결 했다. 

 

아직 많은 문제를 풀어보지 못해 점화식 세우는 것이 익숙하지 않아 오래걸렸다.

그렇게 어려운 문제는 아닌데 확실히 해당 유형을 많이 풀어봐야 됨을 느낄 수 있었다.

 

www.acmicpc.net/problem/2579

2579번: 계단 오르기

점화식을 세우면 사실상 끝나는 문제이다. 하지만 점화식을 세울 때 dp[i][j] = ?? 여기서 행과 열이 어떤 의미를 하는지 정확히 알고 있어야

원하는 값을 얻을 수 있다. 

 

1. 점화식 세울 때 해당하는 행과 열이 어떤 의미를 가지는지 생각하며 세우기

 

2. 초기 dp값 넣어주기 및 예외사항 해결

 

위 처럼 i, j 를 어떤 값으로 생각 할 지는 본인의 몫이고 사람마다 다를 수 있다. 위를 토대로 점화식을 세워보자면

dp[i][0] = max(dp[i-2][0], dp[i-2][1]) + step[i] 이 된다. ( j가 0일 때 1번연속, 1일때 2번연속이다.)

1번연속이라는 말은 이전 계단을 밟지 않았다는 말이다. 그러면 2번째 전의 계단에서 최댓값과 해당 계단의 값을 더한 것이 dp[i][0]가 된다.

dp[i][1] = dp[i-1][0] + step[i] 두번째로 밟은 것은 이전 계단을 밟았다는 말이므로 이렇게 성립이 된다.

 

하지만, 의문이 하나 있다. 왜 항상 최댓값으로 갱신이 될까? 위의 max(dp~~) 이 과정에서 항상 최선의 값으로 업데이트를 해주기 때문에

각 배열은 [j]를 기준으로 항상 최대 값을 유지할 수 있게 된다.

 

from sys import stdin

std = stdin.readline

N = int(std())

step = []
for i in range(N):
    step.append(int(std()))

dp = [[0 for i in range(2)] for j in range(N)]

dp[0][0] = step[0]
if N >= 2:
    dp[1][0], dp[1][1] = step[1], step[0]+step[1]

for i in range(2, N):
    dp[i][0] = max(dp[i-2][1], dp[i-2][0]) + step[i]
    dp[i][1] = dp[i-1][0] + step[i]

print(max(dp[N-1]))

 

 

이와 비슷한 문제로는 '포도주 시식' 문제가 있다

www.acmicpc.net/problem/2156

2156번: 포도주 시식