[ tip ]
같이 공부하는 분께서 알려주신 건데, 일차원 배열만을 고집하기 보다는 이차원 배열도 적당히 섞어가며 생각해보면 좋은 답이 나올 수 있다고 하셔서, dp문제를 다음 2가지 방법으로 생각해보는 연습을 해보면 좋을 듯 하다.
1. 하나의 배열을 가지고 값을 추적하면서 값 업데이트.
2. 이중배열을 사용해서 각각의 경우의 수를 따지기.
1463 1로 만들기
여느 dp 문제가 그렇듯, 코드는 간단한데 이것을 생각해내기가 매우 어려웠다. 이 문제를 못푼 가장 큰 이유는 내가 dp문제를 풀 때 항상 top down 식으로 생각했던 것이었다. 첫번째 수와 두번째 수가 주어지면 점화식을 세우기 수월하므로 이것을 bottom up 상향식 풀이로 풀었어야 했는데 무조건 값 n에서 시작해서 내려가려고 하다보니 자꾸 이상한 방식으로 풀었던 것 같다.
핵심은 3번 조건인 "1을 뺀다" 부분과 1,2번 조건인 3과 2로 나누는 부분을 각각 처리해주는 것이었다. 쉽게 말해, 최악의 경우 n에서 1을 n-1번 빼서 1을 만드는 경우가 있으므로 일단 그 경우라고 생각해두고 만약 3이나 2로 나누어져서 그 결과값이 1을 뺀 값보다 연산횟수가 작다면 그것을 채택하는 방식이었다.
예를 들어 2라고 하면 dp[2] = 1이다. 3이라고 하면 dp[3] = 1이다. 여기까지는 한번에 되는데 만약 dp[10]이라면?? 이것은 두가지 경우가 있다. 일단 dp[9]가 2이므로 dp[10]은 for문 첫줄에 의해 3으로 초기화 된다. 그럼 if문을 봐야하는데, 2로 나누어떨어지므로 dp[i//2]+1과 비교해보아야 한다. dp[i//2]는 dp[5]이고 이 값이 3이므로 if문에서 dp[10]은 4가 된다. 그런데 기존에 초기화 시켜놓았던 dp[10]은 dp[9]+1이므로 3인데, 4보다 작으므로 dp[5]+1을 채택하지 않고 dp[9]+1을 채택한다. 이런 방식으로 하나씩 쭉 초기화를 해주고, n까지 초기화 해주어야 하므로 for문을 n+1까지 돌게 된다. 그리고 마지막에는 dp[n]만을 출력해주면 된다.
* 포인트는 상향식 풀이법과 min을 사용해줌으로써 오히려 더 큰 값이 dp[i]에 할당되는 것을 방지해주는 부분이었다. 코드에는 중복처리라고 작성해놓았는데, 이는 dp[i]에 이미 작은 값이 있는데 오히려 더 큰값이 할당되는 것을 방지해주겠다는 의미였다. 모든 문제가 그렇듯 알고보면 쉬웠다 ...
n= int(input())
# 초기화, n=1일 때 연산 횟수가 0이므로 모두 0으로 초기화 하였음.
dp = [0] * (n+1)
# 처음 두 수를 알고있기 때문에 상향식 풀이
for i in range(2, n+1):
dp[i] = dp[i - 1] + 1 # 초기화 느낌이고 아래 if문에서 조정해주는 것
# 중복 처리 방지를 위해 min 처리
# 즉, for문 첫줄에서 dp[i]를 정의한 값보다 dp[i//3] + 1이 작다면 그것을 선택.
# 2로 나눌 때도 같은 맥락
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2] + 1)
print(dp[n])2579 계단 오르기
먼저 코드를 보자.
N = int(input())
stair = [0]*301
for i in range(N):
stair[i]=int(input())
DP = [0]*301
DP[0] = stair[0]
DP[1] = stair[0]+stair[1]
DP[2] = max(stair[0]+stair[2], stair[1]+stair[2])
for i in range(3, N):
DP[i] = stair[i] + max(DP[i-3] + stair[i-1], DP[i-2])
print(DP[N-1])stair에 저장하고, dp에 점수 합을 저장한다. dp[0]은 첫 계단이므로 무조건 stair[0]이고, 두번째 계단까지의 최대합인 dp[1]도 두 계단을 모두 밟는게 반드시 최대이므로 stair[0]과 stair[1]을 모두 넣어준다. dp[2]는 0 1 2를 모두 밟을 수 없으므로 0 2거나 1 2 중에서 최대값을 넣어준다.
이렇게 초기화 한 후 for문에서 index 3부터 할당을 해주는데, 일단 dp[i]는 i번째 계단을 밟은 상태이므로 stair[i]를 넣어주고 시작한다. 핵심은 max( dp[i-3] + stair[i-1] , dp[i-2] ) 이다. 아래 그림을 보자.
빨간 체크 표시가 i라고 하자. i번째 계단을 밟았다면 주의할 것은 전계단과 전전계단을 밟았는지를 확인하는 것이다. 그래서 이 두가지 경우로 나누었다.
1) 만약 전 계단을 밟았다면(오른쪽 별표), 전전계단을 밟을 수 없으므로 한칸 건너 뛰어서 해당 칸(왼쪽 별표)까지의 최대합을 가져오면 된다. 그렇기 때문에 i-3번째의 dp값과 i-1번째의 계단점수를 가져온다. 그리고 마지막엔 i번째 계단 점수를 dp[i]에 넣어준다. // 만약 dp[i-1]로 퉁쳐버린다면, 오류가 나는데 예시는 다음과 같다.
10 20 15 25일 때 15를 밟았을 때 최대합은 20+15 = 35이므로 dp값도 35가 된다. 근데 만약 25를 밟았을 때의 dp값을 dp[i-1] + stair[i]라고 해버린다면 dp[i-1] = 20+15 = 35이므로 연속해서 3개의 수를 밟게 된다. 따라서 dp[i-1]로 퉁치면 안되고, dp[i-3] + stair[i-1] 이라고 적어주어야 한다. 즉, dp[i] = dp[i-3] + stair[i-1]이라고 해줌으로써 자연스럽게 stair[i-2]를 제외해줌으로써 3계단을 연속해서 밟는 것을 제외시켜주는 것이다.
2) 만약 전계단은 안밟고, 전전계단을 밟았다면 해당 자리의 dp값을 바로 가져온다. 이 경우 연속 3계단을 밟을 경우 자체를 제외한 경우의 수이므로 1번처럼 stair을 고려할 필요 없이 바로 해당 자리의 dp값을 바로 가져온다. 그리고 마지막에 stair[i]를 더해준다.
▶ 최대합을 구해야하므로 이렇게 해서 구한 두 값중에 큰 값을 가져오면 된다.
