uang's blog

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

문제의 조건 

1. k 는 2보다 크거나 같고, 9보다 작거나 같다

2. k+1개의 숫자는 서로 다른 숫자이다

3. k개의 부등호에 맞는 값 중 최대값, 최소값을 구해야 한다

부등호에 '<=', '>=' 이 존재하고 서로 다른 숫자라는 조건이 없었다면, 경우의 수가 1e10 이 돼 TLE이 나겠지만, 

서로 다른 k+1 개의 수를 찾기 때문에 (k+1)! 의 경우의 수만 찾으면 된다.

처음에는 재귀함수를 통해 백트랙킹으로 풀었다.

소스코드 (백트랙킹)

숫자가 최대 10개이므로 비트마스크로 사용한 숫자를 체크하며, 조건이 맞지 않으면 재귀를 탈출하고, 

k+1 개의 숫자를 다 채우면 1을 리턴하면서 종료된다.

최솟값은 0부터 시작해서 찾아야하고, 최댓값은 9부터 시작해서 내려가며 찾아야하기 때문에

같은 재귀라도 반복문을 달리 사용해야하는 번거로움이 있었다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
int k;
char karr[11];
string min_="", max_="";
bool inline chk(int a, char c, int b){
    return c == '>' ? a>b : a<b;
}
string num(vector<int>& ans){
    string s = "";
    for(int i=0; i < ans.size(); i++){
        s += ans[i] + '0';
    }
    return s;
}
int solve(vector<int>& ans, int visited, int p, int ismax){
    if(p == k) {
        return 1;
    }
    int cur = ans[p];
    int init = ismax ? 9 : 0;
    int iter = ismax ? -1 : 1;
    int end = ismax ? -1 : 10;
    for(int pp1=init; pp1 != end; pp1+=iter){
        if(visited & (1<<pp1))
            continue;
 
        if(chk(cur, karr[p], pp1)){
            ans.push_back(pp1);
            if(solve(ans, visited | (1<<pp1), p+1, ismax))
                return 1;
            ans.pop_back();
        }
    }
    return 0;
}
string solve_(int i, int ismax){
    int visited = 0;
    vector<int>ans;
 
    ans.push_back(i);
    visited |= (1<<i);
    if(solve(ans, visited, 0, ismax)){
        return num(ans);
    }
    return "";
}
int main(){
    scanf("%d", &k);
    for(int i=0;i<k;i++){
        scanf(" %c", &karr[i]);
    }
 
    for(int i=0; i<10; i++){
        min_ = solve_(i, 0);
        if(min_ != "") break;
    }
 
    for(int i=9; i>=0; i--){
        max_ = solve_(i, 1);
        if(max_ != "") break;
    }
    printf("%s\n%s\n", max_.c_str(), min_.c_str());
    return 0;
}

풀다보니 최소값은 0~k 의 숫자, 최대값은 9~9-k 까지의 숫자만 사용하면 부등호를 만족하는 순서를 찾을 수 있기 때문에,

k 가 9인 경우 최대 10! 까지만 돌기 때문에 조합으로 풀 수 있겠다 생각됐다.

소스코드 (조합)

조합으로 푸니 코드가 깔끔해졌다.. 진작 이렇게 풀걸

처음부터 조합으로 풀 생각을 할 수 있도록 문제 해결 전략을 잘 세워야겠다..

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int k;
char karr[10];
bool inline chk_(int a, char c, int b){
    return c == '>' ? a>b : a<b;
}
int chk(vector<int>& cand){
    for(int i=0; i<k; i++){
        if(!chk_(cand[i], karr[i], cand[i+1]))
            return 0;
    }
    return 1;
}
int main(){
    scanf("%d", &k);
    for(int i=0; i<k;i++)
        scanf(" %c", &karr[i]);
 
    vector<int> min_ = vector<int>(k+1), max_ = vector<int>(k+1);
    for(int i=0; i<=k; i++){
        min_[i] = i;
        max_[i] = 9-i;
    }
 
    do{
        if(chk(min_)) break;
    }while(next_permutation(min_.begin(), min_.end()));
 
    do{
        if(chk(max_)) break;
    }while(prev_permutation(max_.begin(), max_.end()));
 
    for(int i=0; i<=k; i++)
        printf("%d",max_[i]);
    printf("\n");
    for(int i=0; i<=k; i++)
        printf("%d",min_[i]);
    printf("\n");
    return 0;
}

 풀이 방법

이 문제는 두 지점 사이의 최소 거울 수를 구하는 문제로, 평소 두 지점의 최단거리를 구할 때 사용하는 BFS 를 응용해 "거리" 대신 "거울 수(방향 전환이 일어나는 수)" 를 사용하여 풀 수 있다고 생각했다.

단순 좌표 (y, x) 뿐만 아니라, 사용된 거울 수 및 이동해온 방향 정보가 필요하므로 새로운 구조체를 정의한다.

struct cell{
    int y, x, num, p_dir;
    cell(int y,int x,int num, int p_dir):y(y), x(x), num(num), p_dir(p_dir) {};
};

이동해온 방향(p_dir)을 저장하는 이유는 거울이 사용되는 지점이 방향이 전환되는 시점이기 때문에, 현재 좌표가 어느 방향에서 왔는지 확인하기 위해 필요하다.

이 구조체를 이용해 사용된 거울 수(num) 이 가장 작은 순으로 queue 에서 가져오기 위해 우선순위 큐를 사용한다.

 우선순위 큐의 Comparator 정의

내가 정의한 구조체에서 max-heap 으로 사용할지  min-heap 으로 사용하지 결정하기 위해 compartor를 정의해야 한다.

방법은 구사과 님의 블로그에 자세히 설명돼있다.

풀이에 사용된 방법은 구조체를 이용해 operator() 를 정의해 사용했다.

struct cmp{
    bool operator()(const struct cell& a, const struct cell& b){
        return a.num > b.num;
    }
};

// 중략

priority_queue< cell, vector<cell>, cmp > pq;

* 참고로 greater 는 작은 값을 먼저, less 는 큰 값을 먼저 리턴한다.

* a.num > b.num 는 greater 와 같고, a.num < b.num 은 less 와 같다.

이렇게 정의된 우선순위 큐를 이용하면, 시작지점에서 거울을 사용하지 않고 최대한 이동하여 탐색한 후,

거울  1개, 2개, k개 사용해서 이동할 수 있는 위치를 순차적으로 탐색할 수 있다.

 소스코드

#include<stdio.h>
#include<vector>
#include<queue>
 
using namespace std;
 
struct cell{
    int y, x, num, p_dir;
    cell(int y,int x,int num, int p_dir):y(y), x(x), num(num), p_dir(p_dir) {};
};
struct cmp{
    bool operator()(const struct cell& a, const struct cell& b){
        return a.num > b.num;
    }
};
 
/*
bool operator<(const struct cell a, const strcut cell b){
    return a.num > b.num;
}
*/
int w,h, sy=-1,sx=-1, dy,dx;
int dix[4] = {-1,1,0,0}, diy[4] = {0,0, -1, 1};
char board[111][111];
bool visited[111][111];
bool dir_check(int a, int b){
    return (a<2 && b<2) || (a>=2 && b>=2)  || a == -1;
}
int main(){
    scanf("%d%d",&w,&h);
 
    for(int i=0;i<h;i++){
        scanf("%s", board[i]);
        for(int j=0;j<w;j++){
            if(board[i][j] == 'C'){
                if(sy != -1 && sx != -1){
                    dy = i, dx = j;
                } else {
                    sy = i, sx  = j;
                }
            }
        }
    }
    priority_queue< cell, vector<cell>, cmp > pq;
    // priority_queue< cell, vector<cell>, greater<cell> > pq;
 
    pq.push(cell(sy, sx, 0, -1));
    while(!pq.empty()){
        cell cur = pq.top();
        pq.pop();
        visited[cur.y][cur.x] = 1;
        if(cur.y == dy && cur.x == dx){
            printf("%d\n", cur.num);
            break;
        }
        for(int i=0;i<4;i++){
            int ny = cur.y + diy[i], nx = cur.x + dix[i];
            if(ny >=0 && nx >=0 && nx < w && ny < h) {
                if(!visited[ny][nx] && board[ny][nx] != '*'){
                    // printf("\tnext : (%d, %d) num : %d, is_plus? : %d\n", ny,nx, cur.num, !dir_check(cur.p_dir, i));
                    pq.push(cell(ny, nx, cur.num + (dir_check(cur.p_dir, i) ? 0 : 1), i));
                }
            }
        }
    }
    return 0;
}