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

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

1132번: 합

 

난이도: solved.ac 골드 3

 

알고리즘 분류

그리디 알고리즘

 

접근 방법

이 문제에서 주의해야 할 점은 맨 앞자리에 위치한 알파벳은 0으로 둘 수 없다는 것이다.

 

일단 이 부분을 고려하지 않고 각 알파벳에 숫자를 배정하는 방법은

 

각 알파벳이 몇의 자리수(1, 10, 100, ...)에 위치했는지를 배열에 저장해주고 그 값이 가장 큰 알파벳 차례대로 9, 8, 7, ... 을 배정하는 것이다.

 

예를 들어

2

CBAEF

ADEC

라는 input이 들어왔다고 해보자.

 

문자열 CBAEF에서는

F는 1의 자릿수, E는 10의 자릿수, A는 100의 자릿수, B는 1000의 자릿수, C는 10000의 자릿수에 있으므로 alpha라는 배열에 이를 저장한다.

알파벳	A	B	C	D	E	F
alpha	100	1000	10000	0	10	1

문자열 ADEC에서는

C는 1의 자릿수, E는 10의 자릿수, D는 100의 자릿수, A는 1000의 자릿수에 있으므로 이를 이전의 alpha 배열에 누적해 적어주면 아래와 같다.

알파벳	A	B	C	D	E	F
alpha	1100	1000	10001	100	20	1

여기서 가장 큰 값인 C에 9, 그 다음으로 큰 값인 A에 8, ... 순서로 배정해 alpha 배열에 곱해준다.

알파벳	A	B	C	D	E	F
alpha	8800	7000	90009	600	100	4

각 알파벳에 숫자를 배정하는 방식은 이렇게 하면 된다.

 

하지만 A부터 J까지의 모든 알파벳이 사용되어서 어딘 가엔 0을 배치해야 하는 경우가 있다. 이때 주의해야 할 점은 처음에 언급했던 것처럼 맨 앞자리에 위치한 알파벳은 0으로 배정할 수 없다는 것이다.

 

이런 경우에 0을 배치하는 경우는 다음과 같다.

 

맨 앞자리에 나오지 않은 알파벳들 중 alpha 값이 가장 작은 것에 0을 배치

 

그리고 해당 알파벳의 alpha 값을 0으로 바꿔 alpha 값이 가장 큰 것부터 9, 8, 7, ... 를 배정하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;
long long alpha[10];	// alpha[0]: A, alpha[1]: B, ... , alpha[9]: J
long long ans;
bool notzero[10];	// 0이면 안되는 알파벳 = 1

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, i, j;
	cin >> N;
	for (i = 0; i < N; i++) {
		string input;
		cin >> input;
		notzero[input[0] - 'A'] = 1;	// 첫 번째 자리에 있는 알파벳은 0이 되면 안 됨
		long long k = 1;
		for (j = input.size() - 1; j >= 0; j--) {
			alpha[input[j] - 'A'] += k;
			k *= 10;
		}
	}
	bool flg = 0;
	for (i = 0; i < 10; i++)
		if (!alpha[i])
			flg = 1;
	if (!flg) {
		// A부터 J까지의 모든 알파벳이 사용된 경우에는 어딘가에 0을 줘야 함
		// 0이 되도 괜찮은 것 중 가장 작은 것에 0을 배정
		long long min = 10000000000000000;
		int idx;	// 0을 배정할 알파벳 index
		for (i = 0; i < 10; i++) {
			if (!notzero[i] && alpha[i] < min) {
				min = alpha[i];
				idx = i;
			}
		}
		alpha[idx] = 0;	// 가장 작은 것에 0 배정
	}
	sort(alpha, alpha + 10, greater<>());	// 내림차순 정렬
	for (i = 0, j = 9; i < 10; i++, j--)
		ans += alpha[i] * j;	// 각 알파벳에 숫자 배정 후 계산
	cout << ans;
}

성능

코드 제출 결과