백준 3687 [C++]

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

3687번: 성냥개비

1. 풀이방법

- 최대값은 쉽습니다. 자릿수를 크게 하는 것이 가장 큰 값을 만드는 것입니다.

 

- 같은 성냥을 사용할 떄, 가장 작은 수를 쓰면 됩니다. 쉬우므로 생략하겠습니다.

 

- 최솟값이 어렵습니다.

 

- dp로 좀 더 쉽게 접근했고 오랜만에 dp하려니까 머리가 너무 안돌아갔습니다 ㅠㅠ

 

- makenum배열에 성냥으로 만드는 수를 넣어놓고, 바텀업으로 아래의 점화식과 같습니다.

 

- for (int i = 9; i < 101; i++) {
           dp[i] = dp[i - 2] * 10 + makenum[2]; //init 설정

               for (int j = 3; j < 8; j++) {
                    dp[i] = min(dp[i], dp[i - j] * 10 + makenum[j]);
                }
    }

 

 

2. 주의사항

- 0으로 시작하면 안된다.

 

- 그러므로 dp[6]은 6으로 초기화 하고 makenum[6]에는 0을 넣습니다.

 

- 즉 makenum[6]은 6 성냥으로 만들 수 있는 수 인데, 이후 점화식에서는 6개의 성냥으로는 0을 만들어 쓰겠다입니다

 

 

3. 나의코드

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

int T, n;
int makenum[9] = { 0, 0, 1, 7, 4, 2, 0, 8, 10 }; //일단 6은 0을 넣어놓자 (초기 값 셋팅 이후에는 6개 성냥으로는 0을 만들어야함)
long long dp[101];

void getmin() {
	for (int i = 1; i < 9; i++) {
		dp[i] = makenum[i]; // 성냥 i 개를 가지고 만들 수 있는 min값
	}
	dp[6] = 6; //0으로 시작하는 것을 방지하기 위해

	for (int i = 9; i < 101; i++) {
		dp[i] = dp[i - 2] * 10 + makenum[2]; //init 설정

		for (int j = 3; j < 8; j++) {
			dp[i] = min(dp[i], dp[i - j] * 10 + makenum[j]);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T,n;
	cin >> T;
	getmin();
	while (T--) {
		cin >> n;
		cout << dp[n];
		cout << " ";
		//가장 큰수
		if (n % 2 == 1) { //홀수
			cout << 7; n -= 3;
		}
		while (n != 0) {
			cout << 1; n -= 2;
		}
		cout << "\n";
	}
	return 0;
}