백준 1074-Z C++
카테고리: BOJ
1074-ZPermalink
입력
첫째 줄에 정수 N, r, c가 주어진다.
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
제한
- 1 ≤ N ≤ 15
- 0 ≤ r, c < 2
예제 입력 1Permalink
2 3 1
예제 출력 1Permalink
11
예제 입력 2Permalink
3 7 7
예제 출력 2Permalink
63
풀이
문제는 이해하기 간단하다.
- 사각형을 4분의 1로 나눈다.
- 그렇게 나누던 사각형이 2*2크기가 되면 Z자로 움직인다.
문제는 간단하지만, 이 문제는 시간제한에 걸릴 수 있는 문제점이 있다.
만약에 하나하나 다 지나간다면 2^15 * 2^15라면 10억에 달하는 답이 나와서 터져버린다.
그걸 위해서. 만약에
2사분면에 원하는 답이 있다면, 1사분면은 건너뛰어도 된다.
그러므로 1사분면의 넓이가 만약 8이라고 하면 8*8로 64이니, count에다가 64를 더해주고 바로 2사분면에서 문제를 풀면된다.
코드
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int countz = 0;
int N, r, c;
void dfs(int startx, int starty, int end) {
int sz = end / 2;//4조각으로 나누기 위한 절반가르기.
if (startx == r && starty == c)
{
cout << countz;//만약에 r행, c열에 도달했다면 출력후
exit(0);//프로그램 종료.
}
if (r < startx + end && r >= startx && c < starty + end && c >= starty)
{
//그 사각형의 행안에 r행이 들어있고, 열 안에 c가 들어있다면.
dfs(startx, starty, sz);//2사분면
dfs(startx, starty + sz, sz);//3사분면
dfs(startx + sz, starty, sz);//1사분면.
dfs(startx + sz, starty + sz, sz);//4사분면
}
else
{//만약에 들어가있지 않다면, 그 사각형 다음에 있는 거니까, 그 사각형이
//가지고 있는 번호만큼 count해주기.
countz += end * end;
}
}
int main() {
cin >> N >> r >> c;
int sz = pow(2, N);//2^N크기 구하기.
dfs(0, 0, sz);//0,0시작. sz는 크기.
return 0;
}
댓글 남기기