백준 1332: 풀자

이 문제는 2달 전에 풀이를 시도했다가, 틀려서 그냥 내버려두었던 문제이다.

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

 

 

풀이가 어려운 것은 아닌데, 내가 이 문제에 붙은 태그로 인해서 되려 더 어려운 길을 걷게 된 것 같다. 그렇기에, 이번에 정리하고자 한다.

 

나는 이 문제를 보자마자, Bruteforce를 떠올렸다. 하지만 N의 길이가 50이라서 잘못했다간 시간 초과가 되지 않을까 두려워서 혹시나 해서 태그를 보니 Bruteforce가 맞았다. 그래서 일단 이전의 Bruteforce 문제들 처럼 재귀함수를 활용하였다. 나는 solve 함수를 다음과 같이 정의하였다.

void solve(int idx, int mn, int mx, int cnt) 
{
	if (mx - mn >= V)
	{
		ans = min(ans, cnt);
		return;
	}
	if (idx + 1 < N)
	{
		int nmn = min(mn, A[idx + 1]);
		int nmx = max(mx, A[idx + 1]);
		solve(idx + 1, nmn, nmx, cnt + 1);
	}
	if (idx + 2 < N)
	{
		int nmn = min(mn, A[idx + 2]);
		int nmx = max(mx, A[idx + 2]);
		solve(idx + 2, nmn, nmx, cnt + 1);
	}
}

// idx: 막 푼 문제
// mn: 지금까지 푼 문제 흥미도의 최솟값
// mx: 지금까지 푼 문제 흥미도의 최댓값
// cnt: 풀이 갯수

아니나 다를까 "시간 초과"가 나왔다. 그렇다면 가지치기를 해보자, 지금까지 쌓아온 값이 ans 값보다 크거나 같아지면 바로 return 하는 코드를 추가하였다.

void solve(int idx, int mn, int mx, int cnt) 
{
	if (cnt >= ans) return; // 추가 내용
	if (mx - mn >= V)
	{
		ans = min(ans, cnt);
		return;
	}
	if (idx + 1 < N)
	{
		int nmn = min(mn, A[idx + 1]);
		int nmx = max(mx, A[idx + 1]);
		solve(idx + 1, nmn, nmx, cnt + 1);
	}
	if (idx + 2 < N)
	{
		int nmn = min(mn, A[idx + 2]);
		int nmx = max(mx, A[idx + 2]);
		solve(idx + 2, nmn, nmx, cnt + 1);
	}
}

결과는? 안타깝게도 또 "시간 초과"이다. 더 이상 나는 가지치기를 할 방도가 떠오르지가 않았다. 결국 나는 여기서 포기하고 방치하였다.

 

그렇게 시간이 지나면서, 몇몇 아이디어를 떠올렸고 시도를 했지만 실패로 끝났었다. 여기선 그것을 적어보려한다.

 

이전에 해결했던 다른 문제에서 써먹었던 방법인데, 값이 범위 내에 있는지 확인하는 방법이다. 그러니까, 여기서는 배열을 순회하는 Bruteforce이지만, 이 방법은 값을 기준으로 Bruteforce하는 방법이다.

for(int l = 0; l < 1000; l++)
	for(int r = l + V; r < 1000; r++)
    	ans = min(ans, solve(0, l, r, 1))

하지만 배열의 첫 번째 값이 이 범위 내에 없으면 바로 답이 0이 되어버려서 이 아이디어는 파기했다. 첫 번째 값을 기준으로 고정해도 비슷하기 때문에 넘어가도록 하자.

 

이 방식을 비롯 다른 접근 방식이 있는지 고민했지만, 이 방식이 그나마 가장 그럴 듯했다, 결국 첫 번째 방식에서 가지치기를 하는 다른 방법이 있지 않을까 고민을 하였다.

 

이번엔 약간 Greedy한 방법인데, 어차피 최솟값을 구해야한다. 그런데, 만약 다음 문제가 내가 지금까지 쌓아올린 범위 내에 있다면? 그냥 넘아가도 되지 않을까? 란 생각이 들었다. 일단 그렇게 시도는 해보았지만, 

 

#include <iostream>
#include <algorithm>
using namespace std;

int ans, A[51], N, V;
bool inRange(int l, int r, int v)
{
	return l <= v && v <= r;
}
void solve(int idx, int mn, int mx, int cnt)
{
	if (cnt >= ans) return;
	if (mx - mn >= V)
	{
		ans = min(ans, cnt);
		return;
	}
	if (idx + 1 < N && !inRange(mn, mx, A[idx + 1]))
	{
		int nmn = min(mn, A[idx + 1]);
		int nmx = max(mx, A[idx + 1]);
		solve(idx + 1, nmn, nmx, cnt + 1);
	}
	if (idx + 2 < N)
	{
		int nmn = min(mn, A[idx + 2]);
		int nmx = max(mx, A[idx + 2]);
		solve(idx + 2, nmn, nmx, cnt + 1);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> V;
	for (int i = 0; i < N; i++) cin >> A[i];
	ans = N;
	solve(0, A[0], A[0], 1);
	cout << ans << '\n';
}

이것 또한 "시간 초과"가 났다. 다만, 지금 와서 생각해보면 예외처리가 미흡해서, 시간 제한이 없더라도 통과가 되지 않았을 확률이 높다.

 

그렇게 나는 고민을 한 끝에, 너무나도 간단하고, 어이없는 아이디어를 떠올렸다.

"visit 체크"

dfs에서 가장 기초적으로 사용하는 visit 배열을 사용하는 것이다.

내가 이 방식을 떠올리지 못했던 이유는 2가지다.

 

첫째, 지금까지 푼 Bruteforce 문제의 특징. 지금까지 풀었던 Bruteforce 문제 중에 visit 배열을 사용하는 문제가 적었다.

둘째, 메모리 계산 실패, 보통 나는 메모리를 잡을 때, 10,000,000 내외로 잡는다. 그런데, 이 문제에서 visit 배열을 사용한다면 50,000,000이란 메모리를 잡게 되고 이건 메모리 초과 위험이 있다고 판단했다.

 

하지만 int형이 아닌 bool형인 만큼 메모리를 덜 잡아 먹을 것 같다란 생각에 미치자마자 코드를 수정하였다.

bool v[51][1001][1001];

void solve(int idx, int mn, int mx, int cnt)
{
	if (v[idx][mn][mx]) return; // visit 체크
	v[idx][mn][mx] = true;
    
	if (cnt >= ans) return;
	if (mx - mn >= V)
	{
		ans = min(ans, cnt);
		return;
	}
	if (idx + 2 < N)
	{
		int nmn = min(mn, A[idx + 2]);
		int nmx = max(mx, A[idx + 2]);
		solve(idx + 2, nmn, nmx, cnt + 1);
	}
	if (idx + 1 < N)
	{
		int nmn = min(mn, A[idx + 1]);
		int nmx = max(mx, A[idx + 1]);
		solve(idx + 1, nmn, nmx, cnt + 1);
	}
}

약간 그리디한 기법도 사용했는데, 기존에 idx + 1과 idx + 2의 순서를 바꿨다. 이러면 이 함수는 값이 적은 것 먼저 재귀를 진행한다. 만약 이전에 똑같은 인덱스와 범위를 가진 재귀함수를 만나면 전보다 더 같거나 많은 값을 가질 테니, 볼 필요없이 바로 return한다.

 

이렇게 시도한 결과 드디어 성공하였다. 지금까지 이 문제로 고생한 것에 허무감을 느낀다...

다음부턴 태그에 얽매이지 말자..

#include <iostream>
#include <algorithm>
using namespace std;

int ans, A[51], N, V;
bool v[51][1001][1001];


void solve(int idx, int mn, int mx, int cnt)
{
	if (v[idx][mn][mx]) return;
	v[idx][mn][mx] = true;
	if (cnt >= ans) return;
	if (mx - mn >= V)
	{
		ans = min(ans, cnt);
		return;
	}
	if (idx + 2 < N)
	{
		int nmn = min(mn, A[idx + 2]);
		int nmx = max(mx, A[idx + 2]);
		solve(idx + 2, nmn, nmx, cnt + 1);
	}
	if (idx + 1 < N)
	{
		int nmn = min(mn, A[idx + 1]);
		int nmx = max(mx, A[idx + 1]);
		solve(idx + 1, nmn, nmx, cnt + 1);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> V;
	for (int i = 0; i < N; i++) cin >> A[i];
	ans = N;
	solve(0, A[0], A[0], 1);
	cout << ans << '\n';
}