[ICPC] Philosopher’s Walk

백준 14956번을 통해 풀어본 icpc 예선 문제!

input크기만 봐도 절대 다 채우는걸로는 안되겠다 싶었다

$ 2^{15}*2^{15}  =2^{30} $ 까지 채워야하는 것에 그 전것도 저장해야하고..

암튼 재귀로 나누어서 풀어보기로 했다

 

어떻게 풀기는 했지만 너무 노가다로 풀어서 시간도 꽤 많이 들었고 아쉽다

처음에 사분면으로 나누는 것은 쉽게 재귀로 구현했다

m 값을 그대로 쓰면 나머지 0일때 처리해주기가 까다로워서 -1을 해주고 시작했다

그렇게 사분면을 나누고 나눈 사분면에 따라 중심값을 이동시켜 주면서 좌표를 찾아내었다

처음에는 주어진 n값의 절반인 (n/2,n/2)가 중점이 되고 그 다음부터는 사분면에 따라 중점 결정!

 

여기서부터 노가다가 시작됐다ㅋㅋㅋ

이렇게 사분면 값을 0~3으로 나타내고 1,2일 때는 변화가 없고 0,3일때만 변화가 있는 것은 쉽게 찾을 수 있었다

까다로웠던 부분은 변화가 한번 생기고 나서 그 이후를 고려해주어야 하는 점이었다

도저히 공간감각이 딸려서 생각이 안나서 결국 이런 그림을 만들어서 노가다를 해보았다

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이렇게 해서 모든 경우의 수를 나누니 정답이었다...

n=2가 되었을 때의 rotate에 따라서 마지막 모양이 달라지니까 그 모양에서 순서를 찾는 것은 또 노가다ㅠㅠ

문제 풀다가 헷갈려서 주석으로 그림도 그려보았다ㅋㅋㅋ

 

#include <stdio.h>
 
int q[4][4][2] = {  {{-1,-1},{-1,1},{1,1},{1,-1}},
                    {{1,1},{-1,1},{-1,-1},{1,-1}},
                    {{1,1},{1,-1},{-1,-1},{-1,1}},
                    {{-1,-1},{1,-1},{1,1},{-1,1}}};
 
int d[4][4][2] = {  {{0,0},{0,1},{1,1},{1,0}},
                    {{1,1},{0,1},{0,0},{1,0}},
                    {{1,1},{1,0},{0,0},{0,1}},
                    {{0,0},{1,0},{1,1},{0,1}}}; // rotate, m, dx, dy
 
int r[4][2] = {{3,1},{2,0},{1,3},{0,2}};// prev->next(0,3)
 
void dfs(int n, int m, int rotate, int x, int y){ // quadrant : 0~3
 
    // rotate 0
    //   __
    //  |  |
 
    // rotate 1
    //   ___
    //  |___
 
    // rotate 2
    //  |   |
    //   ---
 
    // rotate 3
    //   __
    //   __|
 
    if(n==2){
        printf("%d %d\n",x+d[rotate][m][0],y+d[rotate][m][1]);
    }
    else{
        int new_n = n/2;
        int quadrant = m / (new_n*new_n);
        int new_m = m - quadrant * (new_n*new_n);
 
        int new_rotate;
 
        if(quadrant==0||quadrant==3) new_rotate = r[rotate][quadrant==0?0:1];
        else new_rotate = rotate;
 
        x += q[rotate][quadrant][0]*(new_n/2);
        y += q[rotate][quadrant][1]*(new_n/2);
 
        dfs(new_n,new_m,new_rotate, x, y);
    }
}
 
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    dfs(n,m-1,0,n/2,n/2);
}

 

컴퓨터보다 노트랑 더 많이 시간을 보냈던 문제

만약 대회에서 이런거 나오면 어차피 컴퓨터 한대니까 컴퓨터 필요한 문제 다른애보고 풀라하고 나는 이런 문제나 노가다 해야겠다

 

이런 그림이 생각나서 약간 슬프지만...