백준 1074번
solved ac 클래스 문제를 전부 풀어보기를 시작했다
재귀를 이용하여 풀었던 Z 문제
풀면서 예전에 Icpc 기출인 philosopher's walk 문제의 쉬운버전이라고 느껴졌다
문제는 오랜만에 알고리즘을 다시 해서 그런가 long long 신경안써서 overflow 일어난 것과 부등호 부주의 했던 점ㅠㅠ
바빠도 일주일에 몇문제씩은 꼭 풀어야지
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#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));
}
|
cs |
현재 상태에서 4등분하여 어느 사분면에 존재하는지 먼저 파악하였다
그리고 N==2인 경우 ( 더 이상 나눌 필요가 없는 경우 ) 에는 몇번째 위치인지 바로 return 해주었다
재귀함수에서 숫자 처리를 할 때 전역으로 많이 하는 습관이 있는데 int형을 반환하는 연습을 하기 좋았던 문제였다
'알고리즘' 카테고리의 다른 글
[C++] 벽 부수고 이동하기 (0) | 2021.07.12 |
---|---|
[C++] 리모컨 (0) | 2021.06.29 |
[프로그래머스] 2021 Dev-matching : 웹 백엔드 개발자 풀이 (0) | 2021.04.28 |
[C++] 프로그래머스 순위 (0) | 2021.04.22 |
[C++] 프로그래머스 전화번호 목록 (0) | 2021.04.07 |