https://www.acmicpc.net/problem/2618
분류 : DP
스프링 공부 및 굑팀 일 하느라 다시한번 미루게 된 알고리즘. 이번생에 8번째로 꾸준히 하자고 다짐하는 중. SJCE 알고리즘 스터디를 부활시키고, 푼 문제를 큐시즘 알고리즘 스터디에서도 인증하며 일석이조!
나는 알고리즘의 꽃은 DP라고 생각한다. 그래서 감 잡기용 DP를 골랐다. 요즘 코테는 DP가 안나오고 구현문제가 많이 나온대서 생각이 많아지긴 한다.
북마크에 2년정도 묵혀있던 dp문제를 풀어봤다. 생각보다 어렵지 않게 풀어서 기분이 좋아졌다. 한번에 AC뜨는 짜릿함에 ps하는 것 같다. 이래놓고 3시간동안 못푸는 문제 만나면 기분이 안좋아지긴 한다.
접근 방법
1000 * 1000의 보드 위에 두 개의 경찰차가 1000번의 move를 가진다.
dp는 bruteforce -> memoization의 방법으로 푼다.
1. naive-bruteforce
첫 번째 장소부터 1000번째 장소까지, 각각의 move에 대해 완전탐색의 경우 2^1000의 방법을 생각해야 한다.
pass
2. dp배열에 두 경찰차의 이전 위치를 저장하는 방식
두개의 경찰차가 이동하는 거리의 합이 value이다.
이전 위치를 (x,y)의 좌표로 저장할 수도 있고, 사건장소의 index로 저장하는 방식이 있다.
전자의 경우 후자의 방식보다 1000^2의 공간이 더 들테니 생각도 하지 말자.
dp[m][n][k] = 1000*1000*1000의 방식을 떠올렸다.
m과n은 첫번째, 두번째 경찰차가 존재하는 index이고, k는 다음 이동해야할 사건의 index이다.
일단 1억을 넘어가기 때문에 안될 거라고 생각했고, 1000*1000의 배열로 풀어야 할 것 같은 직감이 들었다.
그래서,
위의 배열에서 k는 불필요한 인자라는 것을 생각했다. 사건의 순서대로 하나의 경찰차가 이동해야하는 로직이므로, m과n중 큰 값이 이전에 해결한 사건이므로, 다음 사건은 max(m,n)+1이 된다.
dp[m][n]으로 해결할 수 있다고 생각했다.
3. 점화식
dp[m][n] = 첫번째, 두번째 경찰차가 존재하는 index으로 정의했다.
다음 이동해야하는 사건은 next=max(m,n)+1이다.
다음 사건으로 첫 번째 경찰차가 가든가, 두 번째 경찰차가 가는 두 가지 경우의 수를 고려하면 된다.
첫 번째 경찰차가 이동하는 경우 dp[next][n] + dist(m,next)이고
두 번째 경찰차가 이동하는 경우 dp[m][next] + dist(n,next)이다.
따라서
dp[m][n] = min(dp[next][n] + calc(m,next), dp[m][next] + calc(n,next)
으로 점화식을 세웠다.
그리고 dp배열이 2^1000이므로 메모이제이션을 해 주면 된다.
사실 점화식을 세우고 푸는건 아니고, 풀면서 세우는 것 같다.
그리고 처음 두 경찰차가 존재하는 위치인 (0,0)과 (N,N)을 사건배열인 li[0], li[1]에 넣어주었다.
solve(0,1)으로 시작할 수 있도록,
4. dp역추적
이 문제는 dp로 최솟값을 계산하는 것 뿐만 아니라, 어떤 경찰차가 선택했는지 역추적을 해야하는 문제이다. 일반적인 dp문제에서 한 단계 더 까다롭다.
역추적이 많이 나오진 않지만, 역추적 문제집을 풀어보면 좋을 것 같다.
역추적의 방법은 여러개가 있는데, 보통 trace 배열을 만들어 놓고 사용한다.
dp_trace[m][n] 배열을 만들어 놓고, 해당 칸에서 어떤 선택을 했는지 저장한다. 그리고 첫 시작인 solve(0,1) 부터 선택의 값에 따라 잘~ 추적하면 된다.
잘~ 추적하는 방법은, print찍어보면 감이 온다. 문제마다 달라서 여러 문제를 풀어보면 좋겠다.
풀이
# m번 사건에서 n번 사건으로 이동하는 거리
def calc(m,n):
ret= abs(li[m][0] - li[n][0])+abs(li[m][1] - li[n][1])
return ret
# 두 경찰차가 각각 최근 m,n번째 사건을 해결했을 때 남은 사건의 이동거리의 최솟값
def solve(m,n):
ret=0
# 다음 사건
next = max(m,n)+1
# 다음 사건이없음
if next == W+2:
return 0
if dp[m][n]!=-1:
return dp[m][n]
# 해당 사건을 첫 번째 or 두번째 경찰차가 해결
calc1 = solve(next,n)+calc(m,next)
calc2 = solve(m,next)+calc(n,next)
if calc1 < calc2:
dp_trace[m][n]=1
dp[m][n]=calc1
else :
dp_trace[m][n]=2
dp[m][n]=calc2
ret = dp[m][n]
return ret
N=int(input())
W =int(input())
li = [[1,1],[N,N]]
for _ in range(W):
li.append(list(map(int,input().split())))
dp = [[-1]*1002 for _ in range(1002)]
dp_trace =[[-1]*1002 for _ in range(1002)]
print(solve(0,1))
## dp 역추적
m,n = 0,1
for i in range(2,W+2):
print(dp_trace[m][n])
if dp_trace[m][n] ==1 :
m=i
else :
n=i풀고보니 플레?! 백준은 난이도 숨겨놓고 푸는걸 추천. 가끔가다 기분좋은 문제가 이렇게 걸린다.
사실 대부분의 문제는 생각한 난이도보다 낮아서 기분 나쁘긴 함.
