[백준 3687] 성냥개비 (C++)

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

3687번: 성냥개비

문제

---

성냥개비는 숫자를 나타내기에 아주 이상적인 도구이다. 보통 십진수를 성냥개비로 표현하는 방법은 다음과 같다.

성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오.

입력

---

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개 이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)

출력

---

각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. 

 

문제 풀이

---

그리디와 dp 둘 다 접근 가능한 문제였다.

2~7에 대한 답을 구한 후 해당 값에 성냥개비 j개(2<=j <=7, 한 숫자를 만들 수 있는 성냥개비의 개수)를 추가로 사용했을 때 나올 수 있는 최댓값과 최솟값을 배열에 저장하는 dp 방식을 사용했다.

long long으로 최댓값을 구하기에는 자리수가 너무 크므로 문자열의 비교가 필요했다.

 

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

string compareBigger(string s1, string s2)
{
	if (s1.length() > s2.length())
	{
		return s1;
	}
	else if (s1.length() == s2.length())
	{
		if (s1 > s2)
		{
			return s1;
		}
		else
		{
			return s2;
		}
	}
	else
	{
		return s2;
	}
}

string compareSmaller(string s1, string s2)
{
	if (s1.length() < s2.length())
	{
		return s1;
	}
	else if (s1.length() == s2.length())
	{
		if (s1 < s2)
		{
			return s1;
		}
		else
		{
			return s2;
		}
	}
	else
	{
		return s2;
	}
}

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

	int T, N;
	cin >> T;
	string* biggest = new string[101];
	string* smallest = new string[101];
	vector<int>* v = new vector<int>[8];
	for (int i = 0; i < 101; i++)
	{
		biggest[i] = "";
		smallest[i] = "";
	}
	v[2].push_back(1);
	v[3].push_back(7);
	v[4].push_back(4);

	v[5].push_back(2);
	v[5].push_back(3);
	v[5].push_back(5);

	v[6].push_back(0);
	v[6].push_back(6);
	v[6].push_back(9);

	v[7].push_back(8);
	for (int i = 2; i <= 7; i++)
	{
		biggest[i] = to_string(v[i].back());
		if (i == 6)
		{
			smallest[i] = "6";
		}
		else
		{
			smallest[i] = to_string(v[i].front());
		}
	}
	for (int i = 2; i < 101; i++)
	{
		for (int j =2; j <= 7; j++)
		{
			if (i + j < 101)
			{
				if (biggest[i + j] == "")
				{
					biggest[i + j] = biggest[i] + to_string(v[j].back());
				}
				else
				{
					string currentNumStr = biggest[i] + to_string(v[j].back());
					biggest[i + j] = compareBigger(biggest[i+j], currentNumStr);
				}
				if (smallest[i + j] == "")
				{
					smallest[i + j] = smallest[i] + to_string(v[j].front());
				}
				else
				{
					string currentNumStr = smallest[i] + to_string(v[j].front());
					smallest[i + j] = compareSmaller(smallest[i+j], currentNumStr);
				}
			}
		}
	}
	for (int i = 0; i < T; i++)
	{
		cin >> N;
		cout << smallest[N] <<" " << biggest[N] << "\n";
	}
	return 0;
}