[백준/BOJ] 백준 3687번 : 성냥개비

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

3687번: 성냥개비

작은 값을 구하는 방법은 bottom-up 다이나믹 프로그래밍 (아래서부터 하나씩 채워가는 다이나믹 프로그래밍)을 이용해 문제를 해결했고, 큰 값을 구하는 방법은 큰 값은 숫자 1과 7로만 이루어져 있다는 것을 이용하여 문제를 해결했다.

 

코드

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

int tc;
vector<string> smallcache(101, "");//정답을 저장
vector<string> smallnumber(8, ""); //들어갈 숫자를 저장

void Pre()
{
	smallcache[0] = "";

	smallcache[2] = "1";
	smallcache[3] = "7";
	smallcache[4] = "4";
	smallcache[5] = "2";
	smallcache[6] = "6";
	smallcache[7] = "8";

	smallnumber[0] = "";

	smallnumber[2] = "1";
	smallnumber[3] = "7";
	smallnumber[4] = "4";
	smallnumber[5] = "2";
	smallnumber[6] = "0";
	smallnumber[7] = "8";
}

//bottom-up 다이나믹 프로그래밍 (아래서 부터 하나씩 채워가는 다이나믹 프로그래밍)
void smallSolve()
{
	//8부터 100까지 적절한 값을 찾는다
	for (int i = 8; i <= 100; i++)
	{
		bool start = true;
		for (int j = 2; j <= 7; j++)
		{
			string left = smallcache[i - j];
			string right = smallnumber[j];

			if (i - j == 1) //1개로 만들 수 있는것은 없다
				continue;

			//해당 값의 처음 값일때
			if (start)
			{
				smallcache[i] = left + right;
				start = false;
			}

			//더 작은 값을 찾았을때
			else
			{
				if (smallcache[i].size() > left.size() + right.size())
					smallcache[i] = left + right;
				else if (smallcache[i].size() == left.size() + right.size())
				{
					if (smallcache[i] > left + right)
						smallcache[i] = left + right;
				}

			}
		}
	}
}

string bigSolve(int n)
{
	if (n == 0)
		return "";

	if (n == 2)
		return "1";

	if (n == 3)
		return "7";

	string ret = "";

	if (n % 2 == 0) //짝수일때
	{
		ret = bigSolve(2) + bigSolve(n - 2);
	}

	else //홀수일때
	{
		ret = bigSolve(3) + bigSolve(n - 3);
	}

	return ret;
}

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

	Pre();
	smallSolve();

	cin >> tc;

	for (int i = 0; i < tc; i++)
	{
		int n;
		cin >> n;

		cout << smallcache[n] << " " << bigSolve(n) << "\n";
	}

	return 0;
}