[백준/c++] 3687번 - 성냥개비

[ 문제 ]

 

 

 

[ 구현 ]

 

성냥개비의 개수가 주어졌을 때 만들 수 있는 가장 작은 수는 DP를 통해 구했고(그리디로 가능하지만 0과 6사이의 예외처리가 머리 아플것 같음)

가장 큰 수는 그리디로 풀었다.

 

int d[10] = { 2,5,5,4,5,6,3,7,6,6 }는 우선 각각의 숫자를 만들어내는 성냥개비의 개수를 저장한 것이다.

 

이를 기반으로 가장 큰 수를 먼저 생각해보면

가장 큰 수는 최대한 많은 숫자를 통해 구성해서 자릿수를 늘리는게 좋으므로

가장 적은 성냥개비를 통해 만들 수 있는 숫자인 1을 계속해서 붙이는 식으로 구성될 것이다.

 

'1'이라는 숫자는 성냥개비가 2개 필요하므로

성냥개비의 숫자가 홀수일 경우 성냥개비가 3개 필요한 숫자인 '7'을 추가적으로 맨 앞에 활용해주면 된다.

 

이때 주의할 점은 자리수가 최대 50자리까지 증가하므로 자료형을 string으로 해야한다.

 

 

 

다음으로 가장 작은 수를 구하는 경우이다.

 

dp배열에는 i개의 성냥개비로 만들어 낼 수 있는 최소 숫자를 저장할 것이다.

 

우선 성냥개비 8개까지로 구성되는 최소의 수들은 직접 구해서 dp배열에 넣어준다.(한 숫자를 구성할 수 있는 최대의 성냥개비 숫자는 '8'인 경우의 7이고, dp[1]은 없는 값)

 

n=100일때 가능한 최소의 숫자를 계산해보면 최대한 8을 많이 넣은 경우

'18888888888888888888'('8' 14개)일 것이다 (100 = 2 + 14 *7)

따라서 최대 15자리의 수임을 미리 예상하고

초기 값을 1e16으로 설정했다.

 

 

이후

for (int i = 9; i <=100; i++)

     for (int j =2; j <=7; j++)

          dp[i] = min(temp, dp[i-j] *10 + j개로 구성하는 숫자 중 최소값)의 점화식으로 풀면 된다.

 

 

예를 들어

dp[9]을 구하려고 할 때

기존에 미리 구해놓은 값인

dp[2]~dp[8]을 활용할 수 있다

 

dp[2]의 값은 1이고 그 뒤에 7개의 성냥개비로 구성하는 8을 이어붙이면

1 * 10 + 8 = 18이 되는 것이다.

 

 

 

 

[ 코드 ]

 

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int t;
int d[10] = { 2,5,5,4,5,6,3,7,6,6 };
long long dp[101] = { 0, 0, 1, 7, 4, 2, 6, 8, 10};

void print_min(int n) {
	cout << dp[n];

	return;
}

void print_max(int n) {
	string x;
	if (n % 2) {
		x += "7";
		n -= 3;
		while (n) {
			x += "1";
			n -= 2;
		}
		cout << x;
		return;
	}

	else {
		while (n) {
			x += "1";
			n -= 2;
		}
		cout << x;
		return;

	}
}

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

	cin >> t;

	int n;

	for (int i = 9; i <= 100; i++) {
		long long temp = 1e16;
		for (int j = 2; j <= 7; j++) {
			if (j == 2) { temp = min(temp, dp[i - j] * 10 + 1); }
			else if (j == 3) { temp = min(temp, dp[i - j] * 10 + 7); }
			else if (j == 4) { temp = min(temp, dp[i - j] * 10 + 4); }
			else if (j == 5) { temp = min(temp, dp[i - j] * 10 + 2); }
			else if (j == 6) { temp = min(temp, dp[i - j] * 10 + 0); }
			else if (j == 7) { temp = min(temp, dp[i - j] * 10 + 8); }
		}
		dp[i] = temp;
	}

	while (t--) {
		cin >> n;
		print_min(n);
		cout << " ";
		print_max(n);
		cout << '\n';
	}


	return 0;
}

 

 

 

[ 마무리 및 느낀 점 ]

 

한 문제에 작은 문제가 2개 들어있는 재밌는 문제였다.