Boj 2666 벽장문의 이동 / 11570 환상의 듀엣 c++

https://www.acmicpc.net/problem/2666

 

벽장문의 이동

문제

길이가 n인 벽장이 있고, 이중에서 2개의 벽장만 열려있다. 이웃한 벽장이 열려있으면 그 칸으로 문을 옮길 수 있다.

문을 옮기는데에는 1만큼의 시간이 걸린다. 벽장을 열고 싶은 순서가 주어질 때 모든 벽장을 열기 위해 걸리는 최소 시간을 구해야 하는 문제이다.

 

(3 <= n <= 20) 

 

 

관찰 & 풀이

 

현재 열어야 하는 칸이 arr[num] 이라고 하자. 현재 칸을 열기 위해서는 열려있는 두개의 벽장문 중에서 하나를 현재 칸 쪽으로 끌어오면 된다.

직접 그려보면 벽장문이 열려있는 두개의 칸이 a, b라고 하고 현재 칸을 arr[num] 이라고 하면 

1. abs(arr[num] - a)

2. abs(arr[num] - b) 

둘 중 하나 만큼 시간이 걸린다는 것을 알 수 있다.

 

즉, 한 벽장칸을 열 때마다 2가지 선택지가 있다는 것이다.

그리고 열리지 않은 벽장의 개수는 최대 18개이다.

때문에, 2^18 가지 경우의 수를 브루트포스로 구해주면 풀 수 있다.(n이 작기 때문에 가능)

 

재귀 함수로 

f(첫번째 열린 칸, 두번째 열린칸, 열어야 하는 칸 인덱스, 누적시간) 으로 구한 후 == f(a, b, num, cost)

num 이 벽장의 개수가 될 때 ans 값을 업데이트하면 풀 수 있다.

 

 

정답코드(재귀)

#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long 
#define MAX 10000000
using namespace std;
int N, a, b, ans = MAX, k;
int arr[22];
void f(int i, int j, int num, int cost) {
	if(num == k) {
		ans = min(ans, cost);
		return;
	}
	f(arr[num], j, num+1, cost + abs(i-arr[num]));
	f(i, arr[num], num+1, cost + abs(j-arr[num]));
}
	
int32_t main() {
	cin >> N >> a >> b >> k;
	for(int i = 0; i < k; i++) {
		cin >> arr[i];
	}
	f(a, b, 0, 0);
	cout << ans;
}

// total : 2 ^ 18

 

 

그런데 기여창을 보니 dp 태그도 있었다.

엥 ? dp?? 

생각도 안해봤는데..

 

3차원으로 dp[a][b][시작인덱스] 로 짜면 된다고 한다.

그래서 짜봤는데 어떻게 짤지 감도 안잡혀서 인터넷 풀이를 참고했다.

 

역시나 top down 방식으로 짜야지 편한 문제였다.

지금까지 바텀업 원툴로 고생을 많이 했기에 이번 기회에 탑다운 dp를 배워놓아야겠다.

 

 

신기했던 점은 보통 바텀업은 작은 부분을 미리 구해놓고 이를 큰 값을 구하는데에 이용하지만, 

탑다운은 우선 내가 구하고 싶은 값을 인자값으로 준 후, 그 다음에 가지치기 하듯이 쪼개어 구한다는 것이다.

 

즉, 선택의 경우가 2가지로 나뉘는 이문제에 적합한 방법이라는 것이다.

 

코드를 참고해보자

 

정답코드(top-down dp)

 

#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long 
#define MAX 10000000
using namespace std;
int a, b, N, k;
int dp[22][22][22], v[22];

int f(int i, int j, int num) {
	if(num == k)return 0;
	if(dp[i][j][k])return dp[i][j][k];
	return dp[i][j][num] = min(abs(v[num]-i) + f(v[num], j, num+1), abs(v[num]-j) + f(i, v[num], num+1));
} 

int32_t main() {
	cin >> N >> a >> b >> k;
	for(int i = 0; i < k; i++)cin >> v[i];
	cout << f(a, b, 0);
}

 

 

 

첫번째 요청에서 첫번째 칸을 이동하는 것이 유리할 지 두번째 칸을 이동하는 것이 유리할 지 가지치기를 하고 있다.

그 다음 부터 두번째 칸, 세번째 칸, ......마지막 칸까지 가지치기를 진행하고 있다.

그 과정에서 이미 구한 값은 다시 계산하지 않도록 dp값을 저장하고 있다.

(여기서 재귀함수의 인자값은 dp배열의 상태를 나타낸다는 것을 알 수 있다.)

 

마지막 값은 다음 칸이 존재하지 않기 때문에 인덱스가 k(0base)가 되는 순간 종료하도록 설계했다.

 

 

 

그런데, 이 문제를 탑다운으로 풀고 나니 예전에 바텀업으로 어거지로 풀었던 문제가 생각났다.

 

 

환상의 듀엣

 

https://www.acmicpc.net/problem/11570

 

문제

두명이 노래를 부르고 있다. 노래는 n개의 음으로 이루어진다.

두명의 사람이 n개의 음으로 이루어진 노래를 나눠부를 수 있다.

이때, 각 사람이 부르는 파트의 연속한 음 사이의 차이의 총 합을 최소화 하려고 한다.

최솟값을 구하시오

(단, 한개의 음만을 부를 때에는 차이가 0이다)

(1 <= n <= 2000)

 

 

관찰 & 풀이

벽장문의 이동과 마찬가지로 시작 위치를 

두 사람이 아무 음도 선택하지 않은 때, 즉 dp[0][0]을 역순으로 채우는 방식으로 구현하면 될 것 같았다.

 

현재 주어진 음을 i가 부를 수도 있고 j가 부를 수도 있기 때문에 2가지로 가지치기하여 더 작은 것만 넘기면 된다.

 

마찬가지로 멜로디의 인덱스가 최대길이인 n(0base) 에 도달했을 때에는 0을 반환해주면 앞선 논리와 완전히 동일해진다.

 

그리고 음을 처음 부를 때에는 차이를 계산하지 않는다.

 

또 주의할 점은 원래 값이 0인 것과 방문되지 않아 0인 것을 구별해주기 위해 dp배열의 초기값을 -1로 두어야 한다는 것이다.

 (앞으로 항상 -1로 초기화하도록 하자.)

 

이런식으로 매번 최솟값만을 넘기는 구조이기 때문에 역추적하기에도 용이할 것 같다.

정답코드

 

#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long 
using namespace std;
int dp[2020][2020], melody[2020], N;

int f(int i, int j, int cnt) {
	if(cnt == N)return 0;
	if(dp[i][j] != -1)return dp[i][j];
	int ret1, ret2;
	ret1 = f(cnt+1, j, cnt+1); 
	if(i > 0)ret1 += abs(melody[i] - melody[cnt+1]);
	ret2 = f(i, cnt+1, cnt+1);
	if(j > 0)ret2 += abs(melody[j] - melody[cnt+1]);
	return dp[i][j] = min(ret1, ret2);
}

int32_t main() {
	fastio
	cin >> N;
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			dp[i][j] = -1;
	for(int i = 1; i <= N; i++)cin >> melody[i];
	cout << f(0, 0, 0);
}

 

아주 유용한 dp 구현 방법을 배워간다.