성냥깨비

www.acmicpc.net/problem/3687

3687번: 성냥개비

#include<iostream>
#include<vector>
#include <string>
#include <math.h>
#include <algorithm>

using namespace std;

long long num[9] = { 0, 0, 1, 7, 4, 2, 0, 8, 10 };


int main() {
	
	int n;

	cin >> n;
	int cnt;

	long long mindp[101];
	long long maxdp[101];

	mindp[0] = 0;
	mindp[1] = 0;
	mindp[2] = 1;
	mindp[3] = 7;
	mindp[4] = 4;
	mindp[5] = 2;
	mindp[6] = 6;
	mindp[7] = 8;
	mindp[8] = 10;



	for (int i = 9; i <= 100; i++) {
		
		for (int j = 2; j <8 ; j++) {
			

			if(j==2){
			
				mindp[i] =  mindp[i - j] * 10 + num[j];
			}
			else {
			
				mindp[i] =min(mindp[i], mindp[i - j] * 10 + num[j]);
			}
		}
	
	}


	for (int i = 0; i < n; i++) {
		
		cin >> cnt;
		cout << mindp[cnt] << " ";
		
		while (cnt) {
			if (cnt % 2 != 0) {
				cout << 7;
				cnt -= 3;
			}
			else {
				cout << 1;
				cnt -= 2;
			}
		}
		cout << endl;
	}



}