[c++][Greedy] 백준 1339번 문제 풀이

풀이

:

 

알고리즘만 잘 세우면 손 쉽게 해결할 수 있는 문제이다.

 

먼저 입력 받은 문자열을 자릿수에 따라 나누어서 map에 저장해둔다.

 

만약 AECDF 를 입력 받았다면 map에 (A,10000) , (E,1000) , (C,100) (D,10) (F,1) 저장해둔다.

그렇게 모든 문자열들을 저장한다. 만약 중복된 값이 나왔다면 더해서 저장한다.

AAC 이런 문자열이 나왔다면 (A, 100) 을저장한 뒤 (A, 10)을 더해서 저장한다. 즉, (A,110)을 저장한다.

 

모든 입력이 끝나고 각 문자마다 second(map의 second 값) 값이 잘 정리되어 있다.

 

(각각의 second 값) * (1~9 사이 값 지정) 들의 전체 합 이 가장 큰 수가 되야 하므로,

second값을 따로 vector에 저장한 뒤, vector를 내림차순 정렬한다.

(vector 0번째 값 *9) + (vector 1번째 값 * 8) +...+ (vector 마지막 값 * ) = 정답이 된다.

 

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

using namespace std;

int main(int args ,char ** argv){

    int N;
    cin >> N;

    string s;

    map<char , int> m;
    vector<int> v;
	
    //입력된 문자열 각 자릿 수 map에 저장
    for(int i = 0 ; i < N ; ++i){
        cin >> s;

        for(int j  = 0 ; j < s.size() ; ++j){
            m[s[j]] += pow(10,(s.size() - j -1));
        }
    }

	//map의 second값 vector에 저장
    for(auto x : m){
        v.push_back(x.second);
    }

	// 벡터 내림차순 정렬
    sort(v.rbegin() , v.rend());
	
    // 최대 값 구하기
    int nin_to_one = 9;
    int total = 0;
    for(auto x : v){
        total += x * nin_to_one--;
    }

    cout << total;
}

 

백준 1339번 문제

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

1339번: 단어 수학