[C] Z

백준 1074번

 

solved ac 클래스 문제를 전부 풀어보기를 시작했다

재귀를 이용하여 풀었던 Z 문제

풀면서 예전에 Icpc 기출인 philosopher's walk 문제의 쉬운버전이라고 느껴졌다

문제는 오랜만에 알고리즘을 다시 해서 그런가 long long 신경안써서 overflow 일어난 것과 부등호 부주의 했던 점ㅠㅠ

바빠도 일주일에 몇문제씩은 꼭 풀어야지

 

#include <stdio.h>
#include <math.h>
 
long long int dfs(long long int N, int r, int c){
    if(N==2){
        if(r==0 && c==0) return 0;
        else if(r==0 && c==1) return 1;
        else if(r==1 && c==0) return 2;
        else return 3;
    }else{
        long long int N_div2 = N/2;
        long long int pow_N = pow(N,2);
        if(r<N_div2 && c<N_div2) return dfs(N/2,r,c);
        else if(r<N_div2 && c>=N_div2) return pow_N/4 + dfs(N/2,r,c-N_div2);
        else if(r>=N_div2 && c<N_div2) return pow_N/2 + dfs(N/2,r-N_div2,c);
        else return 3*pow_N/4 + dfs(N/2,r-N_div2,c-N_div2);
    }
}
 
int main(){
    long long int N,c,r;
    scanf("%lld %lld %lld",&N,&c,&r);
    long long pow_N = pow(2,N);
    printf("%lld\n",dfs(pow_N,c,r));
}

 

현재 상태에서 4등분하여 어느 사분면에 존재하는지 먼저 파악하였다

그리고 N==2인 경우 ( 더 이상 나눌 필요가 없는 경우 ) 에는 몇번째 위치인지 바로 return 해주었다

재귀함수에서 숫자 처리를 할 때 전역으로 많이 하는 습관이 있는데 int형을 반환하는 연습을 하기 좋았던 문제였다