[백준] No.3687 - 성냥개비 (C++, DP)

문제

 

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

3687번: 성냥개비

 

풀이

 

solved.ac 난이도: Gold 2

 

가장 큰 수와 가장 작은 수를 만드는 방법을 나누어서 생각해보자.

 

1. 가장 큰 수 만들기 (그리디)

 

가장 큰 수를 만들기 위해서는 무엇보다 수의 자릿수를 늘리는 게 최선이다.

예를 들어 성냥개비로 만들 수 있는 가장 큰 한자리 수인 9를 만들기 위해서는 6개의 성냥개비를 써야 한다.

하지만 성냥개비 6개로 1을 3개 만들어 3자리 수 111을 만드는 것이 훨씬 큰 수를 만들 수 있다.

 

따라서 주어진 성냥이 짝수인 경우 성냥을 가장 조금 사용하는 '1'만을 이용하는 것이 가장 큰 수를 만들 수 있다.

홀수인 경우 1 다음으로 가장 적은 성냥으로 만들 수 있는 7(성냥 3개 소모)을 가장 앞자리 수로 사용하고 나머지 성냥으로는 모두 1을 만들어 준다.

 

결과적으로 n개의 성냥으로 만들 수 있는 최댓값은

짝수: 111....11(n/2개의 1)

홀수: 7111...11( 7 + (n-3)/2개의 1)

 

 

2. 가장 작은 수 만들기 (DP)

 

큰 수를 그리디로 만들 수 있어 작은 수도 그리디를 이용해 해결하려 할 수도 있는데, (제가 그랬습니다...)

성냥을 각 자릿수에 최대한 많이 써서 수를 만드는 것은 다음과 같은 케이스들에서 문제가 발생한다.

 

 

성냥이 10개인 경우

3개 + 7개 = 78

4개 + 6개 = 40

5개 + 5개 = 22

...

 

성냥이 11개인 경우

4개 + 7개 = 48

5개 + 6개 = 20

...

 

성냥이 17개인 경우

3개 + 7개 + 7개 = 788

...

5개 + 6개 + 6개 = 200

 

따라서 각 자리수에 성냥을 할당하는 모든 경우를 구해보아야 한다.

여기서 쓰고 남은 성냥이 n개일 때 미리 구해 놓은 최솟값을 재사용 가능하므로 메모이제이션을 활용하자.

 

dp[n]을 n개의 성냥으로 구성 가능한 최솟값이라고 하자.

이번 자릿수를 i(2~7)개의 성냥으로 구성하면 dp[n]은 다음과 같이 구할 수 있다.

dp[n] = min(dp[n], dp[n-i] + num[i])

 

여기서 num[i]는 i개의 성냥으로 만들 수 있는 가장 작은 한자리 수를 의미한다.

단, 0은 가장 앞자리 수가 될 수 없으므로 num[6] = 0 이지만 dp[6] = 6 임을 주의하자.

 

코드

 

	#include<iostream>
	#include<vector>
	#include<string.h>
	using namespace std;
	typedef long long ll;
	ll dp[101];
	void MakeMaxNum(vector<int>& v, int remain_stick) {
	if (remain_stick == 0)
	return;
	if (remain_stick == 3) {
	v.push_back(7);
	return;
	}
	v.push_back(1);
	MakeMaxNum(v, remain_stick-2);
	return;
	}
	void PrintRev(vector<int>& v) {
	for (int i = v.size() - 1; i >= 0; i--)
	cout << v[i];
	}
	int main() {
	ios_base::sync_with_stdio(0);
	int min_num[8] = { 0,0,1,7,4,2,0,8 };
	int test_num;
	cin >> test_num;
	memset(dp, 0x7f , sizeof(dp));
	dp[1] = 9; dp[2] = 1; dp[3] = 7; dp[4] = 4; dp[5] = 2; dp[6] = 6; dp[7] = 8;
	for (int i= 8; i<=100 ; ++i)
	for (int j = 2; j<=7 ; ++j)
	dp[i] = min(dp[i], dp[i-j]*10 + min_num[j]);
	while (test_num--) {
	vector<int> max_v;
	int stick;
	cin >> stick;
	cout << dp[stick] << ' ';
	MakeMaxNum(max_v, stick);
	PrintRev(max_v);
	cout << '\n';
	}
	return 0;
	}

view raw [BaekJoon]_3687_성냥개비.cpp hosted with ❤ by GitHub