문제

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

---

풀이

오답

바구니에 0~9까지의 숫자가 적힌 공이 하나씩 있고, 거기서 공을 하나씩 꺼내 쓴다 생각하고 문제를 풀어봤다. arr 배열에는 바구니에 담긴 각 공의 개수를 저장했다. 그리고 6과 9는 교차가 가능하므로 별도로 처리를 해주었다.

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

const int MAX = 10;
vector<int> arr(MAX, 1);
int cnt = 1;

void initArray() {
	fill(arr.begin(), arr.end(), 1);
}

void handleSpecialCase(int num) {
	if(arr[15 - num] == 0){
		cnt++; // 한 세트 더 필요
		initArray();
	}else{
		// 6과 9를 교차해서 사용 
		arr[15 - num]--; 
	}
}

int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0);

	string s; 
	cin >> s; 

	for(auto ch: s){
		int num = ch - '0';
		
		if(arr[num] == 0) {
			if(num == 6 || num == 9){
				handleSpecialCase(num);
			}else{
				cnt++;
			}
		}else{
			arr[num]--;
		}
	}

	cout << cnt; 
	
	return 0;
}

내가 발견하지 못한 히든 케이스가 있었다. 이렇게 풀면 66666 에 대해서 필요한 세트 개수의 최솟값이 2가 나온다. 하지만, 답은 3이다.

해설

참고: https://karen0117.tistory.com/80

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

const int MAX = 10;
int freq[MAX]; 

int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0);

	string s; 
	cin >> s; 

	int ans = -1; 
	for(auto ch: s){
		int num = ch - '0';
		freq[num]++;

		// 문자의 최대 빈도수 -> 필요한 세트 개수
		if(num != 6 && num != 9){
			ans = max(ans, freq[num]);
		}
	}

	// 6과 9는 교차되기 때문에 필요한 세트 개수는 
	// 두 숫자의 빈도수 합을 2로 나누고 반올림 한 값이다. 
	// ex) 666666 -> 696969 (3), 66666 -> 69696 (3) 
	ans = max(ans, (freq[6] + freq[9] + 1) / 2); 

	cout << ans; 
	
	return 0;
}

6과 9가 교차되지 않는다면 66666을 만들기 위해 필요한 최소 세트 개수는 5개이다. 하지만, 6과 9를 교차해서 사용하면 69696 으로 최소 3개의 세트만 있으면 된다.

따라서, 6과 9를 같은 수로 취급하고 빈도 수를 합한 다음에 2로 나누고 반올림 하면, 필요한 최소 세트 개수를 구할 수 있다!