[Algorithm/C++] 완전 탐색 (Brute-force Search): 백준 2839번, 1436번 문제 풀이

완전 탐색 (Brute-Force) 알고리즘에 대해서는 저번에도 다룬 적 있다. 

반복문을 이용해서 가능성이 있는 모든 숫자를 대입해 정답을 찾는 것이 완전 탐색 알고리즘이다.

오늘은 이 알고리즘을 다룬 백준의 두 가지 문제를 풀어보도록 하자.

이 문제들은 완전 탐색을 사용하지 않고 풀려고 하면 복잡해진다. 

필자도 이 두 문제들을 '규칙을 찾아서' 풀려고 하다가 여러 번 막혀서 포기했었다.

하지만 완전 탐색이 얼마나 단순하면서 편리한 알고리즘인지 익힌 뒤로는 금방 해결할 수 있었다.

 

 

---

 

1. 1436번 : 영화감독 숌

문제 설명

666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그다음으로 큰 수는 1666, 2666, 3666,....이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"과 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수)와 같다.

숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

 

입력

첫째 줄에 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

 

1436번: 영화감독 숌

 

 

해설

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

int main() {
	int N = 0;
	cin >> N;

	int count = 0;

	for (int i = 666; ; i++) {
		string S = to_string(i);
		if (S.find("666") != string::npos) count++;
		if (count == N) {
			cout << i;
			break;
		}
	}

	return 0;
}

필자는 처음 이 문제를 봤을 때 규칙을 찾기 위해 666이 들어간 수많은 숫자를 나열했었다. 666,1666,2666... 하지만 이렇게 규칙을 찾아내는 것보다 단순하게 숫자를 1부터 대입해 보면서 찾아가는 완전 탐색으로 알고리즘을 구현하는 것이 훨씬 현명하다는 것을 깨달았다. 

 

count 정수는 몇 번째 영화 제목인지 나타낸다.

666부터 시작해 1씩 늘리면서 차례대로 666이 포함된 숫자가 나오면 count를 늘리고, 

count와 N이 같다면 해당 숫자가 바로 N번째 영화 제목이라는 것을 알 수 있다.

 

이때 666이 포함된 정수인지 확인하기 위해서 필자가 사용한 방법은, 

매 반복문마다 i를 string으로 변환해서 string의 find 함수를 사용해 string에 "666"이 있는지 확인하는 것이다.

find 함수는 해당 값을 찾으면 값의 itr 값을 반환하고, 찾지 못하면 npos(쓰레기값)을 반환하기 때문에 

if 문을 사용해서 find 함수의 반환 값이 npos가 아니면 666을 찾았다는 것으로 간주한다.

 

 

 

2. 2839번: 설탕 배달

문제 설명:

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

입력:

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

 

출력:

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

2839번: 설탕 배달

 

해설

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

int main() {
	int N = 0;
	cin >> N;
	
	int min_total = 999999;

	for ( int i = 0 ; ; i++) {
		if (3 * i > N) break; // [1]
		for ( int j = 0; ; j++) {
			if (3 * i + 5 * j == N) {
				if (min_total > i + j) min_total = i + j;
			}
			if (3 * i + 5 * j > N) break; // [2]
		}
	}
	if (min_total == 999999) cout << -1; // 초기값이 변하지 않았으면 -1 출력
	else cout << min_total;

	return 0;
}

우선 3kg 설탕 봉지 개수 i와 5kg 설탕 봉지 개수 j를 가지고 for문 두 개를 활용해 완전 탐색 알고리즘을 구현했다.

i와 j의 합의 최솟값을 구하는 것이므로 min_total 변수를 사용해 for문 내부에서 해당값을 갱신하는 방식으로 찾아나갔다.

 

이 코드를 구현할 때 가장 헷갈렸던 부분은 '두 중첩된 for문의 break를 어떻게 구현해야 할지'였다.

여기서 포인트는 'for문을 실행할수록 설탕을 더 얹는다'는 것이다.

[1] 우선 바깥 for문에서는 5kg 봉지 없이 3kg 봉지 만으로 N 값을 능가하면, 설탕을 더 얹는 j for문을 시도할 이유가 없으므로 break 한다.

[2] 안쪽 j for문도 비슷한 원리로 두 설탕 봉지 무게 합이 N 값을 능가하면 더 이상 설탕을 더 얹을 필요가 없으므로 break 한다.

 

 

 

그럼 오늘의 공부 끝!