[BAE/<JOON> 문제풀이] 3687. 성냥 개비

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

3687번: 성냥개비

서론

휴일이라 쉬운거 골라야하는데 DP는 이상하게 문제만 보면 다 쉬워보인다. 막상 짜면 코너케이스도 많고 심지어 점화식 자체가 잘못된 경우도 있음.. 솔직히 이 문제 고르기 전으로 시간 되돌리고 싶다.

풀이

점화식은 사용한 성냥 개수와 그에 따라 만들어지는 수의 [만들어진 숫자 중 0을 제외한 가장 작은 수], [만들어진 숫자 개수] 가지 정보를 활용했다.

큰 수의 경우는 가장 앞에 0이 오면 안된다는 제약 조건을 신경 쓸 필요가 없다. 만들 수 있는 숫자를 내림차순으로 배열할 것이기 때문에 절대 0이 맨 앞에 올 가능성이 없기 때문이다.

큰 수를 만드는 점화식은 다음과 같다.

1. 새로 만든 배열 ( dp[i - 현재 숫자에 사용되는 성냥개비 수] ) 의 숫자 개수가 이전에 만든 배열 ( dp[i] ) 의 개수보다 많은 경우 무조건 갱신
2. 새로 만든 배열과 이전에 만든 배열의 길이가 같은 경우 현재 숫자가 큰 것으로 갱신

정말 간단하다.

 

작은 수를 만들 때 제약이 상당히 귀찮다. 기본 로직은 큰 수 만들 때와 같지만 여러 조건들이 추가된다.

어차피 숫자마다 몇개를 만들었는지 저장하고 오름차순으로 배열할 것이기 때문에 만드는 순서는 중요하지 않다.

그래서 다음과 같은 추가 조건식으로 숫자 생성부터 0을 맨 앞에 둘 수 없도록 했다.

 

T = 현재 새로 추가할 성냥개비 숫자

newarr = 새로 만든 배열 ( dp[현재 사용할 성냥개비 개수 - T만드는데 사용한 성냥개비 개수] 에 z / cnt 갱신 )

current = 기존 배열 ( dp[현재 사용할 성냥개비 개수] ; 여기에 계속 갱신 )

z = 배열 중 0을 제외한 가장 작은 숫자 ( 없는 경우 0 )

cnt = 만든 숫자 개수

• newarr.z == 0 && T == 0 인 경우 추가하지 않음
• newarr.cnt + 1 < current.cnt 인 경우 무조건 갱신
• newarr.cnt + 1 == current.cnt 인 경우
   - newarr.z < current.z 인 경우 무조건 갱신
   - newarr.z == current.z 인 경우 배열 전체를 검사하며 작은 숫자가 더 많은 쪽으로 갱신

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct nd {
	vector<int> pd = vector<int>(10);
	int cnt = 0;
	int z = 0; // 제일 앞에오는 숫자 중 제일 작은거
};
bool cmp(const vector<int>& a, const vector<int>& b) { // a < b == true
	for (int i = 0; i < 10; i++) {
		if (a[i] == b[i]) continue;
		if (a[i] > b[i]) return true;
		else return false;
	}
}
int main() {
	int tc; cin >> tc;
	vector<int> t = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 }; // 숫자 개수가 가장 중요함
	while (tc--) {
		int n; cin >> n; 
		vector<nd> dp(n + 1, { vector<int>(10), 2100000000, 0 });
		dp[0].cnt = 0;		
		for (int i = 2; i <= n; i++) {						
			for (int j = 0; j <= 9; j++) {
				if (i < t[j] || dp[i].cnt < dp[i - t[j]].cnt + 1) continue;
				if (j == 0 && dp[i - 6].z == 0) continue;
				if (dp[i - t[j]].cnt + 1 == dp[i].cnt) {					
					auto cur = dp[i - t[j]];
					cur.cnt++;  cur.pd[j]++; cur.z = cur.z < j || j == 0 ? cur.z : j;
					if (cur.z == 0) cur.z = j;
					if (cur.z > dp[i].z) continue;
					if (cur.z < dp[i].z) {
						dp[i] = cur;
					}
					else {
						dp[i] = cmp(cur.pd, dp[i].pd) ? cur : dp[i];																
					}
				}
				else {
					dp[i] = dp[i - t[j]];
					dp[i].cnt++; dp[i].pd[j]++; dp[i].z = dp[i - t[j]].z < j || j == 0 ? dp[i - t[j]].z : j;
					if (dp[i].z == 0) dp[i].z = j;
				}
			}
		}
		dp[n].pd[dp[n].z]--;
		cout << dp[n].z;
		for (int i = 0; i < 10; i++) {			
			for (int j = 0; j < dp[n].pd[i]; j++) {
				cout << i;
			}			
		}
		cout << " ";
		dp = vector<nd>(n + 1, { vector<int>(10), 0, 0 });
		for (int i = 2; i <= n; i++) {
			for (int j = 0; j <= 9; j++) {
				if (i < t[j] || dp[i].cnt > dp[i - t[j]].cnt + 1) continue;
				dp[i] = dp[i - t[j]];
				dp[i].cnt++; dp[i].pd[j]++;
			}
		}
		for (int i = 9; i >= 0; i--) {
			for (int j = 0; j < dp[n].pd[i]; j++) {
				cout << i;
			}
		}
		cout << "\n";
	}
}