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

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

3687번: 성냥개비

 

DP와 Greedy 문제다.

 

제한된 성냥개비를 모두 이용하여 만들 수 있는 가장 작은 수와 가장 큰 수를 찾는 문제다.

자릿수가 커질 것이기 때문에 숫자가 아닌 문자열을 이용해 계산했다.

 

가장 큰 수의 경우 자릿수를 제일 크게 늘려야 한다.

1을 만들 때 2개가 필요하고 7을 만들 때 3개가 필요하므로 두 개만을 이용해 홀수 짝수인 경우를 고려했다.

dp[2] = "1", dp[3] = "7" 만 초기값으로 지정해주면 이후부터는 뒤에 1을 추가해주면된다.

dp[i] = dp[i - 1] + "1" 이라는 점화식을 사용할 수 있다.

 

가장 작은 수의 경우 성냥개비를 최대로 사용하는 8을 많이 넣는 것이 관건이었다.

7까지는 한자리수로 규칙은 없다.

8부터 11까지도 규칙은 없다.

12부터 규칙이 생기는데 점화식을 세우면 dp[i] = dp[i - 7] + "8"이 된다.

(8을 만들기 위해서 성냥개비 7개 필요하기 때문이다)

이때 dp[17]에서 "200"으로 예외가 생기는데 점화식 대로면 "228"이어야 한다.

 

다른 풀이가 있을 것이라고 생각하지만 나는 17까지 배열에 직접 저장했다.

 

#include <iostream>
using namespace std;

int n;
string dp[101];
string dpa[101];

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

	dp[2] = "1";
	dp[3] = "7";
	dp[4] = "4";
	dp[5] = "2";
	dp[6] = "6";
	dp[7] = "8";
	dp[8] = "10";
	dp[9] = "18";
	dp[10] = "22";
	dp[11] = "20";
	dp[12] = "28";
	dp[13] = "68";
	dp[14] = "88";
	dp[15] = "108";
	dp[16] = "188";
	dp[17] = "200";

	for (int i = 18; i < 101; i++)
		dp[i] = dp[i - 7] + "8";

	dpa[2] = "1";
	dpa[3] = "7";
	for (int i = 4; i < 101; i++) 
		dpa[i] = dpa[i - 2] + "1";

	cin >> n;
	while (n--) {
		int a;	cin >> a;
		cout << dp[a] << " " << dpa[a] << "\n";
	}

}

 

초반 값을 배열에 저장할 때, 이 값이 맞는건지 확신이 안돼서 계산 오류가 많았다.