[C++]백준 - 1074번 문제

1074번: Z (acmicpc.net)

1074번: Z

 

1074번 : Z

---

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

 

입력

---

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

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

분할 정복 문제입니다.

 

2진수로 생각해서 풀어봅시다.

 

일단, 입력받은 배열이 2 * 2일 수도 있고, 8 * 8일수도 있지만,

 

아무튼 아래처럼 4등분 하겠습니다.

 

우리는 여기서 r과 c를 입력 받았는데, r행 c열이 몇 번 구역에 해당하는 지 알아야 합니다.

 

일단 예를 들어서 2번 구역이라고 생각해볼까요?

 

그러면, 우리는 2를 2진수로 변환한 "10"을 기억해두고, 2번 구역으로 갈 것입니다.

 

2번 구역을 확대해보면 또 4등분을 할 수 있을 것입니다.

 이제, 우리는 2번 구역 내에서 r행 c열이 몇 번 구역에 해당하는 지 알아야 합니다.

 

일단 예를 들어서 3번 구역이라 생각해보겠습니다.

 

그러면, 우리는 3을 2진수로 변환한 "11"을 아까 기억한 10 뒤에 붙이고 3번 구역으로 갑니다.

 

현재까지 기억된 2진수 = "1011"

 

그런데, 만약 3번 구역이 더 이상 쪼갤 수 없다면 여기서 알고리즘이 끝나게 될 것입니다.

 

 

실제로 우리가 구한 수는 2번째 구역 내의 3번째 수

 

 

즉, 11입니다.

 

아까 기억한 2진수를 볼까요? "1011"을 10진수로 변환하면?

 

11이므로 정답입니다.

 

이렇게 구하시면 됩니다.

 

 

코드

---

#include <iostream>
using namespace std;

int main()
{
	int N, r, c;
	scanf("%d %d %d", &N, &r, &c);
	long long ans = 0;
    
    //4개씩 분할 정복 Bit 연산
	for (int i = N - 1; 0 <= i; i--)
	{
		ans <<= 2;
		ans += (r >> i << 1) + (c >> i);
		r &= ~(1 << i);
		c &= ~(1 << i);
	}

	printf("%lld", ans);
	return 0;
}

 

그 외

---