[BOJ]1339번: 단어 수학 (c++)

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

1339번: 단어 수학

 

방법 1: 자릿값을 먼저 계산하여 가중치로 활용하고, 가중치 * 숫자 합계 구하기

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    
    // 알파벳별 자릿값(가중치)을 저장할 벡터
    vector<int> weight(26);
    for (int i = 0; i < N; ++i)
    {
        string word;
        cin >> word;

        int w = pow(10, word.size() - 1);
        for (char c : word)
        {
            weight[c - 'A'] += w;
            w /= 10;
        }
    }

    // 내림차순 정렬
    sort(weight.begin(), weight.end(), greater<>());

    // 가중치 * 숫자 합계 구하기
    int sum = 0;
    for (int i = 0, num = 9; num >= 0; ++i, --num)
    {
        sum += weight[i] * num;
    }

    cout << sum;

    return 0;
}

 

 

방법 2: 입력된 순서를 일종의 자릿값으로 사용하여, 순열로 최대값 찾기

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N;
	cin >> N;
	vector<string> words(N);
	
	// 알파벳이 처음으로 입력된 순서를 저장할 벡터
	// 알파벳의 정렬 자릿값
	vector<int> alpha(26, -1);
	int cnt = 0;
	for (int i = 0; i < N; ++i)
	{
		cin >> words[i];
		for (char c : words[i])
		{
			if (alpha[c - 'A'] < 0)
			{
				alpha[c - 'A'] = cnt++;
			}
		}
	}

	// cnt : 알파벳 입력 갯수
	// 알파벳 입력 순으로 cnt개의 숫자를 10 - cnt부터 9까지 매긴다
	vector<int> numbers(cnt);
	for (int i = 0; i < cnt; ++i)
	{
		numbers[i] = 10 - cnt + i;
	}

	// 순열로 가장 큰 합계를 구한다
	int max_sum = 0;
	do {
		int sum = 0;
		for (string wd : words)
		{
			int num = 0;
			for (char c : wd)
			{
				num *= 10;
				num += numbers[alpha[c - 'A']];
			}
			sum += num;
		}

		max_sum = max(max_sum, sum);

	} while (next_permutation(numbers.begin(), numbers.end()));

	cout << max_sum;

	return 0;
}

 

 

방법 1은 O(N) 이고, 방법 2는 O(N!)이다. (N <= 10)

방법 2로 BOJ에서 돌려봤을 때 500ms이상이 나왔다.

c++을 공부한 이후로 처음 본 수치 ㅋㅋ

 

 

처음에 가중치를 단순히 1, 2, 3, .. 이렇게 순위로만 매길 생각을 해서 좀 고생을 했다.

어차피 합계를 구할 것이라면 아예 자릿값을 미리 계산해버립시다.