[BOJ-1107]리모컨

풀기는 풀었는데..... 

이 문제 푼 사람 중 나 혼자 메모리 부자인 것 같다........ㅋㅋㅋㅋㅋㅋㅋㅋ

거의 푼 사람들 보니 메모리가 2000~5000KB 밖에 사용하지 않았는데... 118,000KB ㅋㅋㅋㅋㅋㅋㅋㅋ 문제 제한 메모리가 128MB 였는데 메모리 초과안뜬게 참 다행(?) 인 것 같다.

여튼.... 이 문제는 요약하자면,

TV가 있고, 리모컨이 있고, 내 현재 채널은 100, 채널은 [0, INF], 

목표 ; 내가 가고 보고싶은 채널(목표채널) 이 있다.

1. 버튼이 있다 ( [ 0, 9 ] , + , - )

2. 근데 부서졌다 ( +, - 버튼은 부서지지 않았다. )

3. 그 버튼 제외하고, 목표채널을 가기 위해 누른다.

이때 버튼을 최소한으로 누른다면 몇 번 눌러야 함?

위가 문제 요약이고 

일단 코드는 개판이지만..... 시간 좀 흐른 다음에 다시 풀어야 봐야겠다..... 

전에 풀었던 로봇 이랑 쪼끔 비슷한 것 같다 순서대로 Q에 넣지않는다면, WA(틀렸습니다!) 을 받았다.

메모리 줄이려고 코드 수정했는데 지금은 또 아무 생각 없는 것 같고......

#include<cstdio>
#include<vector>
#include<queue>
#include<memory.h>
#include<utility>
#define make_pair(a,b) mp(a,b)
using namespace std;
 
typedef vector<bool> VB;
typedef vector<int> VI;
typedef vector<VI> VVI;
 
const int MAX = 1500000;
int gap = 10000000;
int goal;
int m;
 
VVI noButton;
int vmap[MAX];
 
struct info{
    int x; // channel
    int c; // count
    info(int xi, int ci):x(xi), c(ci){}
};
 
int min2(int a, int b){
    return (a<b)?a:b;
}
 
int main(){
    scanf("%d%d", &goal,&m);
    VB use = VB(10, true);
    VVI noButton = VVI(12, VI(0,0));
    for(int i = 0 ; i < m ; i++){
        int un;
        scanf("%d", &un);
        use[un]=false;
    }
 
    for(int i = 0 ; i < 10 ; i++){
        if(use[i]){
            noButton[1].push_back(i);
        }
    }
 
    memset( vmap, -1, sizeof(vmap) );
 
    // one button
    // two button
    // ...
    // n button -> min(Goal)
    VB chaLen = VB(20, false);
    chaLen[0] = true;
    queue<info> Q;
    Q.push(info(100,0));
    vmap[100] = 0;
    while(!Q.empty()){
        info here = Q.front(); Q.pop();
 
        int c = here.c; // button count
        int x = here.x; // channel
 
        if(x == goal) break;
 
        if(0 <= x){
            if(x-1 >= 0){
                if(vmap[x-1]==-1){ // 
                    Q.push(info(x-1, c+1));
                    vmap[x-1] = c+1;
                }
            }
            if(vmap[x+1]==-1){
                Q.push(info(x+1, c+1));
                vmap[x+1] = c+1;
            }
        }
 
        if(0 <= c && c < 10){ // c == 0 .... 
            if(chaLen[c+1] == false){
                chaLen[c+1] = true;
 
                if(c+1 == 1){
                    for(auto iter = noButton[1].begin() ; iter != noButton[1].end() ; iter++){
                        int channel = *iter;
                        if(vmap[channel] == -1){
                            vmap[channel] = c+1;
                            Q.push(info(channel, c+1));
                        }
 
                        for(auto i2 = noButton[1].begin() ; i2 != noButton[1].end() ; i2++){
                            if(channel*10 + (*i2) >= 10){
                                noButton[2].push_back(channel*10 + (*i2));
                            }
                        }
                    }
                }
                else if(1 < c+1 && c+1 < 7){ // 2 c -> 1 -
                    for(auto iter = noButton[c+1].begin() ; iter != noButton[c+1].end() ; iter++){
                        int channel = *iter;
                        if(vmap[channel] == -1){
                            vmap[channel] = c+1;
                            Q.push(info(channel, c+1));
                        }
 
                        for(auto i2 = noButton[1].begin() ; i2 != noButton[1].end() ; i2++){
                            noButton[c+2].push_back(channel*10 + (*i2));
                        }
                    }
                }
 
                // 1자리 일때 돌고
                // 2자리 일때 돌고
                // 3자리 일때 돌고
 
            }
        }
    }
 
    printf("%d", vmap[goal]);
    return 0;
}
 
// 37% WA