백준3687 성냥개비 - C++

보기에는 간단한데 생각보다 난이도가 높은 문제이다.

 

가장 작은 수는 dp로, max는 그리디로 접근한다.

#include <stdio.h>
#include <string.h>
int t, n;
char max[102];
long long dp[101];
//성냥 개수 있을때 만들 수 있는 최대 수
char GreedyMax[8] = { 0x0,0x0,'1', '7', '4', '5','9','8' };
long long min[9] = { 0,0,1,7,4,2,0,8,10 };
void makeMax(int n,int idx) {
	if (n == 0) {
		return;
	}
	if (n % 2) {
		max[idx] = GreedyMax[3];
		makeMax(n - 3, idx + 1);
	}
	else{
		max[idx] = GreedyMax[2];
		makeMax(n - 2, idx + 1);
	}
	return;
}
void makeMin() {
	for (int i = 1; i <= 8; i++) {
		dp[i] = min[i];
	}
	dp[6] = 6;

	for (int i = 9; i <= 100; i++) {
		dp[i] = dp[i - 2] * 10 + min[2];
		for (int j = 3; j < 8; j++) {
			long long tmp = dp[i - j] * 10 + min[j];
			if (dp[i] > tmp) {
				dp[i] = tmp;
			}
		}
	}
}

void solve() {
	memset(max, 0, sizeof(max));
	makeMax(n,0);
}

int main() {
	scanf("%d", &t);
	makeMin();
	for (int loop = 1; loop <= t; loop++) {
		scanf("%d", &n);
		printf("%lld ", dp[n]);
		solve();
		printf("%s\n", max);
	}
	return 0;
}