[순열,조합] 백준 2529: 부등호

2529번: 부등호

 

1. 0-9 까지 숫자 중 k+1 개를 골라 만들 수 있는 모든 '조합'을 구한다.

 

2. 1에서 구한 조합으로 구현 가능한 모든 '순열'을 구한다.

 

3. 부등호와 맞는지 비교한다.

 

먼저, 조합을 구하는 코드는 다음과 같이 구현했다. 모든 조합을 구해서, 그 조합들을 다시 vector<vector<int>> 의 vector 요소로 저장하였다.

void makeCombination(vector<vector<int>> &combinations, vector<int> &numbers, vector<int> &currentComb, int start, int len)
{
    if(currentComb.size()==len)
    {
        vector<int> result;
        for(int i=0;i<currentComb.size();i++)
        {
            result.push_back(currentComb[i]);
        }
        combinations.push_back(result);
    }

    for(int i=start;i<numbers.size();i++)
    {
        currentComb.push_back(numbers[i]);
        makeCombination(combinations, numbers, currentComb, i+1, len);
        currentComb.pop_back();
    }
}

 

그 다음, 다시 이 모든 조합들을 활용해 순열을 구한다. 매 순열마다, 그 순열을 매개변수로 하여 정답을 찾는 함수를 수행한다.

makeCombination(combinations, numbers, combination, 0, k+1);

    for(int i=0;i<combinations.size();i++)
    {
        sort(combinations[i].begin(), combinations[i].end());
        do
        {   
            checkPermutation(combinations[i], comparisions);
        } while (next_permutation(combinations[i].begin(), combinations[i].end()));        
    }

 

전체 코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>

using namespace std;

vector<int> minVector;
vector<int> maxVector;
long long minValue = LLONG_MAX;
long long maxValue = LLONG_MIN;

void makeCombination(vector<vector<int>> &combinations, vector<int> &numbers, vector<int> &currentComb, int start, int len)
{
    if(currentComb.size()==len)
    {
        vector<int> result;
        for(int i=0;i<currentComb.size();i++)
        {
            result.push_back(currentComb[i]);
        }
        combinations.push_back(result);
    }

    for(int i=start;i<numbers.size();i++)
    {
        currentComb.push_back(numbers[i]);
        makeCombination(combinations, numbers, currentComb, i+1, len);
        currentComb.pop_back();
    }
}

void checkPermutation(vector<int> &permutation, vector<char> &comparision)
{
    int comparisionIdx = 0;

    for(int i=0;i<permutation.size()-1;i++)
    {
        int a = permutation[i];
        int b = permutation[i+1];

        if(a<b && comparision[comparisionIdx]=='<')
        {
            comparisionIdx++;
        }
        else if(a>b && comparision[comparisionIdx]=='>')
        {
            comparisionIdx++;
        }
        else return;
    }

    long long answer = 0;
    for(int i=0;i<permutation.size();i++)
    {
        answer = answer*10+permutation[i];
    }

    if(minValue>answer)
    {
        minValue = answer;
        minVector = permutation;
    }

    if(maxValue<answer)
    {
        maxValue = answer;
        maxVector = permutation;
    }
}

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

    int k;
    cin>>k;

    vector<char> comparisions;

    char charInput;
    for(int i=0;i<k;i++)
    {
        cin>>charInput;
        comparisions.push_back(charInput);
    }

    vector<int> numbers;
    for(int i=0;i<10;i++)
    {
        numbers.push_back(i);
    }

    vector<vector<int>> combinations;
    vector<int> combination;

    makeCombination(combinations, numbers, combination, 0, k+1);

    for(int i=0;i<combinations.size();i++)
    {
        sort(combinations[i].begin(), combinations[i].end());
        do
        {   
            checkPermutation(combinations[i], comparisions);
        } while (next_permutation(combinations[i].begin(), combinations[i].end()));        
    }

    for(int i=0;i<maxVector.size();i++)
    {
        cout<<maxVector[i];
    }
    cout<<"\n";
    for(int i=0;i<minVector.size();i++)
    {
        cout<<minVector[i];
    }

}

 

 

내가 이 문제에서 빠진 함정은 다음과 같다.

 

 

1. 수학적으로 '모든 조합을 구해서 각 조합의 모든 순열을 구하자!'는 생각은 금방 했지만, 코드로 구현하는 데 애를 먹었다. 다소 매크로처럼 쓸 수 있는 순열(next_permutation)과는 다르게 아직도 조합은 좀 헷갈린다.

 

2. 가장 큰 경우의 수가 976543210이다. 따라서 int 범위로는 감당 못 하는 수라 long long을 써야 한다. 습관적으로 int로 작성하였다가 낭패를 봤다.

 

3. minVector, maxVector를 업데이트할 때 그냥 minVector = permutation 과 같은 식으로 하면 되는데 굳이 함수 내에서 따로 벡터를 만들어서 다시 붙여넣으려고 하는 헛수고를 좀 했다. 그냥 deep copy 되기 때문에 편하게 하자.