[C++] G5 백준 2666 - 벽장문의 이동

1. 문제 링크

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

소요 시간 : 1시간

시도 횟수 : 1

 

2. 문제 설명

난이도 : G5

사용 알고리즘 : DP

벽장을 최소로 움직이는 횟수를 구하는 문제

 

3. 풀이 방식

DP문제를 풀어보고 싶어서 문제를 골랐는데 처음엔 greedy 느낌도 나서 당황했다.

공책에 끄적여보며 n=7, 문(2,6) 호출 순서 (4,3,1,6) 이렇게 해보니(왼쪽 오른쪽 거리가 같게) greedy가 아니라는걸 알 수 있었다.

근데 이 문제, 내가 알던 기존의 DP와는 뭔가 달랐다.

BFS에서 큐에 다음 데이터를 넣거나 DFS에서 재귀적으로 호출하듯이 이 문제 또한 다음 단계마다 2가지 경우의 수를 따져야 하는 느낌

말하고 보니 이진 트리 느낌도 난다.

이게 왜 DP일까, 이런 것도 DP인가? 라는 생각으로 문제를 풀어봤다.

 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int len;
int dp[21][21][21];
vector<int> v;

int check(int i, int left, int right) {
	if (i >= len) return 0;
	int now = v[i];
	if(now<=left) dp[i][left][right] = abs(left - now) + check(i + 1, now, right);
	else if(now>=right) dp[i][left][right] = abs(right - now) + check(i + 1, left, now);
	else {
		int mv_left = abs(left - now) + check(i + 1, now, right);
		int mv_right = abs(right - now) + check(i + 1, left, now);
		dp[i][left][right] = min(mv_left, mv_right);
	}
	return dp[i][left][right];
}

int main() {
	int n, left, right;
	cin >> n >> left >> right >> len;
	for (int i = 0; i < len; i++) {
		int t;
		cin >> t;
		v.push_back(t);
	}
	cout << check(0, left, right);
}

다음 벽장이 left보다 왼쪽에 있을 때는 왼쪽 문을,

right보다 오른쪽에 있을 때는 오른쪽 문을 움직이고자 했다.

left, right의 사이에 있을 경우에는 둘 중 최솟값을 저장하기로 했다.

여기서 함수를 재귀적으로 한 번 더 호출을 해서, 이후 상황에 최소로 움직일 수 있는 값을 찾는 방식이다.

 

<오늘의 TMI>
기숙사 냉장고가 너무 작아요