취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3687번 문제인 성냥개비이다.
문제는 아래 링크를 확인하자.

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

0으로 숫자가 시작하면 안 된다는 조건에 신경써야하는 문제이다.

성냥개비 1개로는 숫자를 한 자리도 만들 수 없고, 2개로는 1, 3개로는 7, 4개로는 4, 5개로는 2와 3과 5, 6개로는 0과 6, 7개로는 8을 만들 수 있다. 8개 이상의 성냥개비로는 한 자리의 숫자를 만들 수 없다.

이런 성냥개비들을 모두 사용해서 가장 큰 수를 만드는 방법은 쉽게 유추할 수 있다.

자릿수가 큰 숫자가 기본적으로 가장 큰 수이므로, 1을 최대한 많이 사용하고, 홀수의 경우 7을 하나 맨 앞에 사용하는 것이 그 답이다.

그렇다면 가장 작은 수는 어떻게 만들 수 있을까?

가장 큰 수와 마찬가지로, 자릿수가 가장 적게 만들어져야 할테니 한 자리에 7개의 성냥개비가 필요한 8을 많이 사용하는 방향을 잡는 것은 맞아보인다.

그 외에, 7로 나눈 나머지에 맞춰 14 이하의 수들에 대하여 미리 가장 작은 숫자들을 입력해주면 문제를 해결할 수 있다.

특히 성냥개비가 12개일 때 나와야하는 수가 어떤 수인지 신경을 쓰자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		int N; cin >> N;
		if (N < 8) {
			if (N == 2) cout << 1;
			else if (N == 3) cout << 7;
			else if (N == 4) cout << 4;
			else if (N == 5) cout << 2;
			else if (N == 6) cout << 6;
			else if (N == 7) cout << 8;
		}
		else {
			int res = N % 7;
			int NN = 0;
			if (res == 1) cout << 10;
			else if (res == 2) cout << 18;
			else if (res == 3) {
				if (N == 10) cout << 22;
				else cout << 200;
				NN--;
			}
			else if (res == 4) cout << 20;
			else if (res == 5) cout << 28;
			else if (res == 6) cout << 68;
			else if (res == 0) cout << 8;

			NN += N / 7 - 1;
			while (NN > 0) {
				cout << 8;
				NN--;
			}
		}


		cout << ' ';

		if (N & 1) {
			cout << 7;
			N -= 3;
		}
		N >>= 1;
		while (N--) cout << 1;
		cout << '\n';
	}
}