(시간초과 풀이)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N, r, c, ans=-1;
void find(int i, int j, int depth){
if(depth == 1){
for(int q=i-1;q<=i;q++)
{
for(int z=j-1;z<=j;z++)
{
ans++;
if(q == r and z == c)
cout << ans << '\n';
}
}
}
else{
find(i/2, j/2, depth-1);
find(i/2, j, depth-1);
find(i, j/2, depth-1);
find(i,j, depth-1);
}
return;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> r >> c;
find((int)pow(2,N)-1, (int)pow(2,N)-1, N);
return 0;
}
- 각 범위를 depth로 두고 타고 들어가서 차례대로 수행하게 하였음
- 모든 범위에 대해 수행하므로 0.5초 시간동안 수행할 수 없음
(정답 풀이)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N, r, c, ans;
void find(int i, int j, int size){
if(i == r and j == c)
{
cout << ans << '\n';
return;
}
if((r >= i and r< i+size) and(c >= j and c < j+size)){
find(i, j, size/2);
find(i, j+size/2, size/2);
find(i+size/2, j, size/2);
find(i+size/2,j+size/2, size/2);
}else
{
ans += size*size;
}
return;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> r >> c;
find(0, 0, (1<<N));
return 0;
}
- 시간 초과 해결
: 모든 사분면에 대해 find하지 않고, 검사해서 안에 없으면 해당 size*size
만큼 더하기
- 로직
1) 현재 좌표에 대해 size만큼의 사각형 범위
안에 r,c
가 있는지 검사
2-1) 있다면, size가 1
이 될 때 까지 찾아 들어간다
2-2) 없다면, 해당 구역은 건너 뛰어야 하므로 size*size
만큼 ans
에 더한다
3) size가 1일 때 우리가 원하는 정답이 나오게 된다