백준 1074-Z C++

Date:     Updated:

카테고리:

태그:

1074-ZPermalink

캡처.PNG

입력


첫째 줄에 정수 N, r, c가 주어진다.

출력


r행 c열을 몇 번째로 방문했는지 출력한다.

제한


  • 1 ≤ N ≤ 15
  • 0 ≤ r, c < 2

예제 입력 1Permalink

2 3 1

예제 출력 1Permalink

11

예제 입력 2Permalink

3 7 7

예제 출력 2Permalink

63

풀이


문제는 이해하기 간단하다.

  1. 사각형을 4분의 1로 나눈다.
  2. 그렇게 나누던 사각형이 2*2크기가 되면 Z자로 움직인다.

문제는 간단하지만, 이 문제는 시간제한에 걸릴 수 있는 문제점이 있다.

만약에 하나하나 다 지나간다면 2^15 * 2^15라면 10억에 달하는 답이 나와서 터져버린다.

그걸 위해서. 만약에

제목 없음.png

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;
}

BOJ 카테고리 내 다른 글 보러가기

댓글 남기기