다른 블로그의 답을 참고해서 풀려고 했었다. 근데 내가 봤던 블로그는 dp로 열어야하는 문의 순서, 열려있는 문 각 2개를 인덱스로 하는 3차원 배열을 정의해두었다. 근데 나는 처음에 이 3차원 배열을 잘 이해 못해서 그냥 dp 안 쓰고 재귀로만 했다.
이렇게.
ans = 10000000
def dfs(open1, open2, depth, cnt):
global ans
if depth == M:
ans = min(ans, cnt)
return
tmp1 = abs(open1 - arr[depth])
tmp2 = abs(open2 - arr[depth])
dfs(arr[depth], open2, depth+1, cnt+tmp1)
dfs(open1, arr[depth], depth+1, cnt+tmp2)
dfs(open1, open2, 0, 0)
print(ans)문제의 크기가 작아서 그런지 맞을 수 있었다! 하지만 찝찝함은 안 없어져용.
나도 dp로 다시 풀어보기 위해 저 분의 dp 정의를 이해해야 했다. 별로 어렵지도 않은데 🙂 엄청 헷갈린다. 남의 코드를 볼 때는 이상하게 조급해지는 것같다.
정말 당연한 것이지만 dp를 삼차원 배열로 정의한 이유는
부분 문제마다 필요한 정보가 3개이기 때문이라는 걸 잊으면 안된다.
- 열어야 하는 문들 중에 몇 번째로 열어야하는 문인지
- 열려있는 문 1
- 열려있는 문 2
1번을 다시 말하자면, 우리가 열어야 하는 문이 입력으로 들어온다. 이렇게
4 # 4개의 문을 열어야한다. (M=4)
3
1
6
5 # 리스트에 [3, 1, 6, 5]로 저장한다.그걸 따로 order라는 리스트에 저장을 해두고 나서 앞에서부터 차례로 문제를 풀어야 하는데, 접근을 인덱스로 하니까 함수의 인자로 orderIdx를 넣어줘야하는 것이다 ㅎㅎ
def solve(orderIdx, open1, open2):
if orderIdx == M:
return 0
if dp[orderIdx][open1][open2] != -1:
return dp[orderIdx][open1][open2]
open1_cnt = solve(orderIdx+1, order[orderIdx], open2) + abs(order[orderIdx] - open1)
open2_cnt = solve(orderIdx+1, open1, order[orderIdx]) + abs(order[orderIdx] - open2)
dp[orderIdx][open1][open2] = min(open1_cnt, open2_cnt)
return dp[orderIdx][open1][open2]구웃 🙆🏻♀️
solve()를 이렇게 정의하면 메인은 밑에처럼 구성하면 된다.
N = int(input())
open1, open2 = map(int, input().split()) # 처음에 열려있는 문
order = [] # 열어야 하는 문 저장해둘 리스트
M = int(input()) # 열어야 하는 문 개수
for _ in range(M):
order.append(int(input()))
# 3차원 dp 선언하기!
# 문에 직접 접근하는 인덱스는 +1 돼있어서 크기를 1씩 늘렸어요.
# M은 열어야 하는 문의 개수라서 그냥 그대로 했어요.
dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(M)]
print(solve(0, open1, open2))c++ 참고한 블로그: https://jaimemin.tistory.com/544
감사합니다.
풀기는 풀었지만 학기 시작하고 그동안 한 거 다 까먹은 거같아서 맘이 아프다. 또 다시 열심히 해야겠다 🏃🏻♂️
