[백준/C++] 단어 수학 (No.1339)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 풀 때, 단순 대입을 이용해 재귀로 풀었다.

그랬더니 단순히 반복문이 10^10이라 시간초과가 걸렸다;;

 

다음으로 생각한 방법은 어차피 수가 최대 10개나오므로 가장 앞자리에 많이 나온 자리수를 이용해 정렬하면 풀 수 있겠다는 생각이 들었다.

 

즉, A라는 문자가 10의 자리에만 2번 나오고 B의 문자가 10의 자리에만 1번 나온다면 당연히 A>B로 수를 대입하는게 더 큰 수를 만들 수 있다는 아이디어다.

 

문제는 수의 개수가 10개라는데서 반례가 발생했다.

만약 A라는 문자가 10의 자리에 2번 나오고 B라는 문자가 10의 자리에 1번, 1의 자리에 10번 나오면 A와 B는 같은 Value를 가지게 된다.

 

그래서 이를 고려해서 문제를 풀었다.

 

먼저 특정 문자 x가 i번자리에 등장하면 i번 자리에 등장한 횟수를 기록한다.

만약 문자 x가 i번자리에 10번 등장하면 i+1번자리에 등장한 것과 같으므로 i번자리에서 등장횟수를 10 빼고, i+1번자리에 등장횟수를 1 더하는 방법으로 구현했다.

 

이후 자리에 따른 등장횟수를 전부 구했다면, 가장 앞 자리에 많이 나온 수가 가장 큰 값을 갖는게 큰 수를 만드는데 유리하므로 이를 기준으로 정렬하면 된다.

 

만약 앞자리에 나온 횟수가 같다면 그 뒷자리에 나온 횟수를 비교해 정렬하면 된다.

 

이후 곱셈을 통해 값을 계산하면 된다.

 

잘 생각해보면 자리에 나온 횟수 [123412] * (수의 value)로 계산이 되므로 자리에 나온 횟수를 미리 계산하는 방법도 있었다...

 

​

[아이디어 정리]

1. x라는 문자가 자리수에 따라 나온 횟수를 계산한다.
2. 이때, x라는 문자가 i번째 자리에 10번 나타나면 i+1번째 자리에 1번 나타난 것과 같으므로 이를 반영한다.
3. 나타난 횟수가 계산이 완료 됐다면 앞자리에 나온 횟수가 많은 순서로 정렬한다.
4. 이후 정렬된 기준에 따라 값을 할당해 최대값을 계산한다.

 

 

Code

 

 

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin >> N;
	vector<string> stV(N);
	map<char, long long> m;
	long long idx = 1;
	string str;
	vector<vector<long long>> V(11,vector<long long>(10,0)); // i번문자가 j번 자리에 있는 경우를 저장함
	for (int i = 0; i < N; i++) {
		cin >> str;
		stV[i] = str;
		for (int j = 0; j < stV[i].size(); j++) {
			if (m[stV[i][j]] == 0) {
				m[stV[i][j]] = idx;
				idx++;
			}
			V[m[stV[i][j]]][stV[i].size()-j-1] += 1;
			if (V[m[stV[i][j]]][stV[i].size() - j - 1] == 10) {
				int jdx = stV[i].size() - j - 1;
				while (V[m[stV[i][j]]][jdx] >= 10) {
					V[m[stV[i][j]]][jdx] -= 10;
					jdx++;
					V[m[stV[i][j]]][jdx] += 1;
				}
			}
		}
	}
	sort(V.begin(), V.end(), [](vector<long long> a, vector<long long> b) {
		for (int i = 9; i >= 0; i--) {

			if (a[i] < b[i]) {
				return true;
			}
			else if (a[i] > b[i]) {
				return false;
			}
		}
		return false;
	});
	long long maxH = 0;
	for (int i = 0; i <= 10; i++) {
		long long tmpH = 0;
		for (int j = 9; j >=0; j--) {
			tmpH *= 10;
			tmpH += V[i][j] * (i-1);
		}
		maxH += tmpH;
	}
	cout << maxH;
	return 0;
}

---

 

계속 틀려서 문제가 뭘까 생각했는데, 지금보니 x문자가 10번 나올 수 있다는 사실을 간과해서 오래 걸렸다... ㅠㅠ

 

 

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