백준 : 1074번, Z

문제 주소 : www.acmicpc.net/problem/1074

정답 비율 : 37.446% (2021.02.19 21:20 기준)

1074번: Z

문제 조건 :

입력 : 차례대로 N, r, c가 주어집니다. (N : 1 ~ 15  |   r, c : 0 ~ 2^N - 1)

출력 : r행 c열을 몇 번째 방문하는지 출력

시간 : 0.5 초

 

문제 풀이 :

다음과 같이 구역을 나눕니다.

< N = 2 일 때 모습 >

 

-> 이렇게 4개 구역을 나누고 해당 좌표가 n번째 구역에 포함될 때 n보다 작은 구역은 지나간 상태이므로 그 구역의 크기만큼 답에 더합니다. 그렇게 더 이상 쪼개 술 없을 때까지 반복하여 답을 구하였습니다.

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

int ans = 0;

void dfs(int Max, int x, int y)
{
	if(Max > 1)
	{
		int x_area = (x < Max / 2 ? 0 : 1);
		int y_area = (y < Max / 2 ? 0 : 1);
		ans = ans + (Max * Max / 4) * (y_area * 2 + x_area);
		
		dfs(Max / 2, x - Max / 2 * x_area, y - Max / 2 * y_area);
	}
}

int main()
{
	int N, y, x, Max = 1;
	
	scanf("%d %d %d", &N, &y, &x);
	
	for(;N;N--)
		Max *= 2;
		
	dfs(Max, x, y);
	
	printf("%d", ans);
} 

 

***

다른 사람의 풀이를 보니 단순 for문 하나에 비트 연산을 이용하여 문제를 풀었습니다.

해당 풀이의 아이디어 해석

num1 & num2 의미는 두 개의 숫자를 and 연산을 하는 것입니다. 이때 num2의 이진수에 1이 하나만 있을 경우에는(0100, 1000 같이 1이 하나만 존재) num1 & num2의 결과가 True이면 num1은 num2보다 크거나 같고 Flase이면 num1이 num2보다 작다라고 해석할 수 있습니다.

 

좋은 코드를 구경하였습니다.