백준 1132: 합

현재 매일매일 알고리즘 문제를 해결 중에 있고, 오늘 기준으로 915일 연속으로 문제를 해결하였다.

하지만 가끔 하고 싶은 말이 있는 문제가 더럿 생긴다. 그래서 자주는 아니지만 시간이 되면 글을 적어보려한다.

 

이번에 다룰 문제는 백준 1132, 합이다.

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

1132번: 합

이 문제는 어디서 본 것 같다. 그렇다 백준 1339와 유사하다.

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

1339번: 단어 수학

일단 이 문제를 언급하고 넘어가자. 만약 숫자 단어가 ABCDE라고 하자 이것을 어떻게 다르게 나타낼 수 있을까?

 

A * (10 ^ 4) + B * (10 ^ 3) + C * (10 ^ 2) + D(10 ^ 1) + E 이런 식으로 풀어낼 수 있다. 우리는 이러한 숫자 단어들의 합을 최대로 내고 싶다. 그러면 어떻게 해야할까? 자릿값을 크게 가지는 알파벳에 큰 숫자를 할당하면 된다.

 

그렇다면? 각 숫자 단어를 위와 같이 풀어 쓰고, 같은 알파벳끼리 합쳐서, 값이 큰 알파벳에 큰 숫자를 할당하면 된다.

그렇게 나는 이렇게 문제를 해결하였다.

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

string W[11];
int C[26], N, D[26], ans = 0, cnt[26];
vector<pair<int, char>> A;
int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> W[i];
		for (int idx = 0; idx < W[i].size(); idx++)
			C[W[i][idx] - 'A'] += pow(10, W[i].size() - idx);
	}
	for (int i = 0; i < 26; i++)
		if (C[i] > 0)
			A.push_back({ -C[i], (i + 'A') });
	sort(A.begin(), A.end());
	for (int n = 9, idx = 0; idx < A.size(); idx++, n--) D[A[idx].second - 'A'] = n;
	for (int i = 0; i < N; i++)
		for (int idx = W[i].size() - 1, d = 1; idx >= 0; idx--, d *= 10)
			ans += D[W[i][idx] - 'A'] * d;
	cout << ans << '\n';
}

이제 다시 1132로 돌아오자. 이 문제에선 추가적으로 앞자리가 0이 되어선 안된다는 제약이 걸려있다.

 

주의해야할 점은 0을 할당하는 것은 ABCDEFGHIJ가 전부 나타나야 할 경우 뿐이다. 그래서 위의 알파벳들이 전부 있을 때, 앞자리가 아니면서, 가장 작은 수를 가진 알파벳에 0을 할당하면 끝이다.... 인줄 알았는데, 문제가 발생했다.

일단 코드를 보자

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;

vector<ll> tmp, arr;
bool Z[10];
int N, sel = 0, cnt = 0;
ll D[10], ans = 0;
string E;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> E;
		Z[E[0] - 'A'] = true;
		for (int idx = E.size() - 1; idx >= 0; idx--)
		{
			D[E[idx] - 'A'] += pow(10, (E.size() - 1 - idx));
		}
	}
	
	for (int i = 0; i < 10; i++)
		if (D[i] > 0)
			arr.push_back(D[i]);
	if (arr.size() == 10)
	{
		for (int i = 0; i < 10; i++)
		{
			if (!Z[i] && arr[sel] > arr[i])
				sel = i;
		}
		swap(arr[sel], arr[0]);
		sort(arr.begin() + 1, arr.end());
	}
	else
		sort(arr.begin(), arr.end());
		
	for (int i = arr.size() - 1; i >= 0; i--) ans += (arr[i] * (9 - arr.size() + 1 + i));
	cout << ans << '\n';
}

코드를 다시 재구성해서, 위의 코드와 다른 부분이 많지만 근본적으론 비슷하다.

 

이 코드가 아니라는 결과를 받았다. 분명 이론도 이해했고, 게시판의 반례도 전부 통과했다. 코드에 이상한 점이 없는지 몇 번씩 확인했지만, 계속 틀렸다는 것이다. 몇 시간동안 코드와 눈싸움을 한 나는 결국 구글링을 하였지만, 이론에 틀린 점은 없었다. 결국 다른 분의 코드를 바탕으로 수정을 가했고, 그렇게 정답을 얻었다.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;

bool f = false;
bool Z[10];
int N, sel = 0;
ll D[10], ans = 0, t = 1;
string E;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> E;
		Z[E[0] - 'A'] = true;
		t = 1;
		for (int idx = E.size() - 1; idx >= 0; idx--)
		{
			D[E[idx] - 'A'] += t;
			t *= 10;
		}
	}

	for (int i = 0; i < 10; i++)
		if (D[i] == 0)
			f = true;
	if (!f)
	{

		ll m = 10000000000000000;
		for (int i = 0; i < 10; i++)
		{
			if (!Z[i] && D[i] < m)
			{
				m = D[i];
				sel = i;
			}
		}
 		D[sel] = 0L;
	}
	sort(D, D + 10, greater<ll>());
	for (int i = 0, j = 9; i < 10; i++, j--) ans += (D[i] * j);
	cout << ans << '\n';
}

 

앞자리를 검증하는 과정에서 잘못되었던 것 같은데, 위의 코드와의 큰 차이점을 잘 모르겠다. 어쨌든 이론도 알고 있으니 넘어가자.

 

 

참조: https://jangkunstory.tistory.com/145

[백준 / C++] 1132번: 합 (그리디 알고리즘, greedy algorithm)