[BOJ] 2643:색종이 올려 놓기

 

 

0. 문제

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

2643번: 색종이 올려 놓기

 

1. 문제분석

- 이 문제는 색종이들을 쌓아올렸을 때, 해당 색종이를 위에 올려 놓을 수 있느냐 없느냐의 여부가 여태까지 쌓아올린 색종이 더미 중 가장 위에 있는 색종이의 가로 세로 길이에 따라 달라진다. 즉, 현재의 경우가 직전의 경우에 영향을 받게 되므로, 동적 계획법(dynamic programming)을 사용해서 문제를 풀어야 했다.

- 또한 색종이들을 경우에 따라 사용 가능한 최대량의 색종이들을 사용해야 하므로, 모든 경우의 수를 탐색해보는 완전탐색이 필요하다. 즉, 매 경우마다 가능 여부를 파악한 뒤 탐색이 더이상 불가능할 때까지 탐색을 이어가야 하므로, 깊이우선탐색(DFS)을 사용해야 했다.

 

2. 유의할 점

- 색종이를 90도씩 회전할 수 있으므로, 직사각형인 각 색종이는 원래 모양, 가로 세로가 바뀐 모양, 총 두 모양으로 사용 가능하다. 처음에는 이를 2차원 dp 배열로 구현하려 하였으나, 입력 단계에서 해당 색종이를 가로 세로가 바뀐 모양으로 한번 더 입력시켜 주어 각 경우를 독립된 경우로 설정하였다. 이 때문에 각 색종이에 대한 방문여부 체크 시, 해당 색종이를 회전시킨 경우에 대해서도 방문여부를 true로 체크해 주어 두 경우가 동시에 접근될 수 없도록 하였다.

- 최초값을 반환하는 경우는 bool형의 flag변수를 지정하여 한번도 또다른 탐색이 이루어지지 않았을 경우를 잡아낸 후, 이 때에 1값을 반환해주도록 설정하였다.

 

3. 소스코드(C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#define endl '\n'
#define INF 987654321
using namespace std;
typedef pair<int, int> ii;

int n, ans = 0;
vector<ii> paper;
vector<bool> vtd;
int dp[200];

int go(int now) {
	int& ret = dp[now];
	if (ret != 0) return ret;
	bool flag = true;
	int now_pair = (now % 2 == 0) ? now + 1 : now - 1;
	vtd[now] = vtd[now_pair] = true;
	for (int i = 0; i < paper.size(); i++) {
		if (vtd[i]) continue;
		if (paper[i].first <= paper[now].first &&
			paper[i].second <= paper[now].second) {
			ret = max(ret, go(i));
			flag = false;
		}
	}
	vtd[now] = vtd[now_pair] = false;
	if (flag) {
		return ret = 1;
	}
	return ret += 1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int ww, hh;
	cin >> n;
	while (n--) {
		cin >> ww >> hh;
		paper.push_back({ ww,hh });
		vtd.push_back(false);
		paper.push_back({ hh,ww });
		vtd.push_back(false);
	}

	for (int i = 0; i < paper.size(); i++) go(i);
	for (int i = 0; i < paper.size(); i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans;
	return 0;
}

 

4. 여담

- 어려워보였으나 생각보다 쉽게 풀렸다. dfs에 스스로 많이 적응된 듯 하다.

- 방문하지 않은 모든 노드를 항상 다 살펴보아야 하기 때문에 시간초과가 날 줄 알았는데, 노드 개수가 적어서 dfs가 가능했던것 같기도 하다.

- KOI 초등부 문제는 대체로 구현은 까다로운 대신, 데이터의 크기가 많지 않은 듯 하다. 구현이 복잡하고 어렵게 만드는 대신, 오기로 깡으로 노가다로 풀면 되는 문제가 은근 있는 것 같다.