BOJ 2666

me

문제에서 여러 상황이 있고, 선택에 따라 최소횟수를 구하는 것이 다르니깐 dp를 이용해야 한다는 점은 명확했다. 앞선 선택 중 작은 횟수에 다음 번의 선택을 더했는다. 지금보니깐 dp가 아니라 그리디 같아졌다. 선택 이후의 상황에 대한 고려도 필요하다.
아무튼 첫 코드는 dp를 이용했지만 단순히 앞의 것을 기억하는 형태를 벗어나지 못했다.

import sys
input = sys.stdin.readline

n = int(input())
open = list(map(int,input().split()))

k = int(input())
looks = [ int(input()) for _ in range(k) ]

dp=[0]*(k+1)
for i in range(1,k+1):
    print(open)
    move1 = dp[i-1] + abs(open[0]-looks[i-1])
    move2 = dp[i-1] + abs(open[1]-looks[i-1])
    if move1 < move2:
        open[0]=looks[i-1]
        dp[i]=move1
    else:
        open[1]=looks[i-1]
        dp[i]=move2
print(dp[-1])
"""
20
1 20
10
10
1
10
1
10
1
10
1
10
1
반례로 틀린다.
"""

others

bottom-up 방식을 써서 해야 한다.
벽장을 이동시킨 후의 상황도 교려해야 한다.
그 순간의 이동 횟수만 고려할 것이 아니라 그 이후의 상황도 고려 해야한다.
문 하나를 선택하고 그 뒤의 것도 고려해야 하므로 다 잘게 쪼갠 뒤 가장 작은 것들을 앞으로 넘겨서 값을 구해야 한다.

dp = [[[-1]*(n+1) for _ in range(n+1)] for _ in range(k)]

# 열려있는 문들 중 몇번째로 열어야 하는 지, 열려있는 문들
def solve(idx, open1, open2):
    if idx == k:
        return 0

    if dp[idx][open1][open2] != -1:
        return dp[idx][open1][open2]

    open1_cnt = solve(idx+1, looks[idx], open2) + abs(looks[idx] - open1)
    open2_cnt = solve(idx+1, open1, looks[idx]) + abs(looks[idx] - open2)

    dp[idx][open1][open2] = min(open1_cnt, open2_cnt)

    return dp[idx][open1][open2]

print(solve(0,open[0],open[1]))