Baekjoon 1138번 한 줄로 서기

문제

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

걸린 시간

02 : 05 : 31

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n;
int taller[11];

void solve(vector<int>& line, int visited[11]){
    // 기저 사례
    if(line.size() == n){
        bool correct = true;
        for(int i = 0; i < n; i++){
            int count = 0;
            for(int j = 0; j < i; j++){
                if(line[i] < line[j])
                    count++;
            }
            if(count != taller[line[i]]){
                correct = false;
                break;
            }
        }
        if(correct){    
            for(int i = 0; i < n; i++)
                cout << line[i] << " ";
            cout << "\n";
            exit(0);
        }
    }
    // 재귀 호출    
    for(int i = 1; i <= n; i++){
        if(!visited[i]){
            visited[i] = 1;
            line.push_back(i);
            solve(line, visited);
            visited[i] = 0;
            line.pop_back();
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> taller[i];
    vector<int> line;
    int visited[11];
    memset(visited, 0, sizeof(visited));
    solve(line, visited);
    return 0;
}

그리디로 풀 수 있다고 하는데 아이디어가 떠오르지 않아 구현으로 풀이했다.

문제의 최대 입력인 10이 주어진다고 했을 때, 전부 줄 세울 수 있는 경우의 수(순열)는 10! = 3,628,800 그리고 문제의 조건에 맞게 나열되었는지를 확인하는 작업은 1부터 9까지의 합 45, 총 10! * 45 = 163,296,000 으로 제한 시간 2초 안에 들 수 있다.