BOJ 1654번: 랜선 자르기 문제로 알아보는 "최적화 문제 결정 문제로 바꿔 풀기"

지난 주 코로나19에 걸려 격리를 하면서 매일 근근이 solved.ac [CLASS 2] 문제만 풀고 있었는데, 순서대로 풀다가 맞닥뜨린 "랜선 자르기" 문제에 의외의 중요한 알고리즘 설계 패러다임이 담겨 있다고 생각해 글을 작성하기로 했습니다.

목차

1. 문제 훑어보기

2. 최적화 문제와 결정 문제

3. 이분 탐색과 매개 변수 탐색

4. BOJ 1654번: 랜선 자르기 (실버 III)

참고한 자료

알고리즘 문제 해결 전략, 구종만

https://book.algospot.com/

알고리즘 문제 해결 전략

알고리즘 트레이닝: 프로그래밍 대회 입문 가이드, 안티 라크소넨

http://www.yes24.com/Product/Goods/108202966

알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드 - YES24

실전 알고리즘 0x13강 이분탐색, BaaaaaaaarkingDog

https://blog.encrypted.gg/985?category=773649 

[실전 알고리즘] 0x13강 - 이분탐색

---

문제 훑어보기

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

1654번: 랜선 자르기

K개의 서로 다른 길이의 랜선을 적절히 잘라 길이가 각각 n인 랜선 N개를 만드는데, 그때 n의 최대값을 계산하는 문제입니다.

 

이 문제를 무식하게 풀 수 있을까요? 이를테면 n을 1부터 1씩 늘려가는 방법 말이죠. 어림잡아 계산해보면 각 n에 대해 최대 10000번씩 더해야 하고, 랜선의 길이는 무려 \(2^{31}-1\)까지 커질 수 있네요... 안 될 것 같습니다. n의 처음 값을 1이 아닌 적당한 값으로 잡고 구현해 보기도 했지만 어김없이 시간초과가 나오더라고요.

 

그렇다면 어떻게 해야 이 문제를 효율적으로 풀 수 있을까요? 앞으로 설명할 패러다임이 이 문제 해결의 키가 됩니다.

최적화 문제와 결정 문제

위 문제와 같이 최적의 해를 구하는 최적화 문제는 답의 경우의 수가 무한합니다. 결정 문제는 예/아니오로 답이 정해지는 문제를 의미하는데, 답의 경우의 수가 2가지죠. 놀랍게도 최적화 문제를 결정 문제로 바꿀 수 있는 상황이 많이 있습니다.

 

예를 들어 최적화 문제인 '랜선 자르기'를 결정 문제로 바꿔 보면 다음과 같습니다.

최적화 문제: optimize() = K개의 서로 다른 길이의 랜선을 적절히 잘라 길이가 각각 n인 랜선 N개를 만드는데, 그때 n의 최대값을 계산하라.

결정 문제: decision(x) = K개의 서로 다른 길이의 랜선을 적절히 잘라 길이가 각각 x인 랜선 N개를 만들 수 있는지 확인하라.

여기서 만약 optimize() 함수가 구현되어 있다면, decision() 함수의 구현은 곧바로 가능해집니다.

int optimize(); // 이미 구현되어 있음
bool decision(int x) {
    return optimize() >= x;
}

optimize()가 반환하는 최대값보다 x가 작거나 같다면 decision(x)는 무조건 참이죠! 따라서 위와 같이 하면 됩니다. 여기서 알 수 있는 점은 결정 문제가 최적화 문제보다 푸는 데 오래 걸릴 수는 없다는 것입니다. 특히 '랜선 자르기' 문제는 결정 문제로 바꿔 풀면 훨씬 빨리 풀 수 있게 되는 트릭이 있습니다. 다음에 소개할 이분 탐색의 응용 덕분입니다.

이분 탐색과 매개 변수 탐색

이분 탐색은 이미 정렬된 배열 안에 특정 원소가 존재하는지 \(O(\log n)\) 시간 안에 탐색하는 알고리즘입니다. 만약 오름차순 정렬된 배열의 정 가운데 원소가 내가 찾는 원소보다 크다면, 그 오른쪽에 있는 모든 원소 역시 더 크므로 비교할 필요가 없겠죠. 이 방법으로 남은 배열을 계속 이분하여 원소를 찾을 때까지 계속합니다.

 

아래는 이분 탐색을 간단하게 구현해 본 것입니다.

int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (arr[mid] == x) {
        // 위치 mid에서 x를 찾음
    }
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid - 1;
}

매개 변수 탐색은 이분 탐색을 결정 문제에 적용한 것입니다. 최적화 문제가 최대값을 구하는 문제이고 가능한 답의 범위가 \([a,b]\)이면, 다음과 같이 매개 변수 탐색을 구현할 수 있습니다.

int lo = a, hi = b;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (decision(mid)) lo = mid + 1; // mid에서 가능하다면, 더 큰 가능한 값을 찾는다
    else hi = mid - 1;
}

BOJ 1654번: 랜선 자르기 (실버 III)

이제 문제를 풀기 위한 모든 이론을 습득했으니 구현해 봅시다!

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define ul unsigned long

bool decision(vector<ul>& lines, int K, int N, int x) {
	ul cutsum = 0;
	for (int i = 0; i < K; i++) {
		cutsum += lines[i] / x;
	}
	return cutsum >= N;
}

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

	// input
	int K, N;
	cin >> K >> N;
	vector<ul> lines(K);
	for (int i = 0; i < K; i++) {
		cin >> lines[i];
	}

	// parametric search
	ul lo = 1, hi = pow(2, 31) - 1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (decision(lines, K, N, mid)) lo = mid + 1;
		else hi = mid - 1;
	}

	// output
	cout << hi;

	return 0;
}

이렇게 보니 생각보다 어렵지 않은 것 같습니다. 패러다임을 안다면 그대로 적용이 되니까요.

---

매개 변수 탐색을 배우고 나니 포케모음 계산기 최적화 코드를 개선할 수가 있겠어요.

고개 숙인 개발자가 되지 않도록 앞으로 알고리즘 공부 열심히 해야겠어요. 그럼 다음 시간에 또 만나요~

 

https://pokemoem.com/calculator

포케모음 :: 8세대 계산기