[백준/C++] 1074번. Z

문제

1074번: Z

---

1. 첫 번째 풀이 (마지막 풀이)

사고 과정

- 상당히 재귀적인 문제다.

- 먼저 4등분으로 나눈다. Z의 순서에 따라, 각각 1, 2, 3, 4평면이라고 하자.

- r행 c열은 넷 중 하나에 속하게 된다.

- 만약 크기가 4x4고(N = 2), r행 c열이 4평면에 있다고 하자. 탐색이 4평면에 도달하려면, 2x2 칸을 세 번 지나야 한다.

- 즉, 2^N 칸을 세 번 지나치므로, 12번 탐색부터 4평면에서 진행된다. (시작이 0이므로)

- 이를 모두 1칸 남을 때까지 반복하면 될 것 같다. base case를 N = 0으로 두고, 이땐 그냥 return 0로.

- 배열의 각 칸에 0, 1, 2, 3을 저장해두고, 이에 각각 2^i(i는 인덱스)를 곱한 후 모두 더하는 방법도 좋아보인다.

- 2진수같기도. 하지만 이왕 재귀로 시작한 거, 재귀로 끝을 보자.

 

1. N, r, c 입력

2. 재귀함수 작성, 매 재귀마다 n이 1씩 줄어들며, 어느 평면에 속하냐에 따라 count를 다르게 리턴

 

코드

#include <cstdio>
#include <cmath>

int prevSearchCount(int n, int r, int c) {
	if (n == 0) {
		return 0;
	}

	int half = std::pow(2, n - 1);

	if (c < half && r < half) {
		return prevSearchCount(n-1, r, c);
	}

	if (c >= half && r < half) {
		return half * half + prevSearchCount(n - 1, r, c - half);
	}

	if (c < half && r >= half) {
		return 2 * half * half + prevSearchCount(n - 1, r - half, c);
	}

	if (c >= half && r >= half) {
		return 3 * half * half + prevSearchCount(n - 1, r - half, c - half);
	}
}

int main() {
	int n, r, c;
	scanf("%d %d %d", &n, &r, &c);
	printf("%d", prevSearchCount(n, r, c));
}

가장 러프한 타입

 

결과

성공~

---

개선

사고 과정

- 알고리즘 측면에선 문제없어 보이고, 코드를 줄여보자.

- 우선 네 리턴값의 차이는, half * half에 몇을 곱하냐. 이건 따로 변수로 지정해줄 수 있겠고

- 재귀 매개 변수로 무엇을 넣느냐. r과 c를 그냥 감소시키면 되지 않을까?

- 결국 r과 c는 half 이상일 때 감소된다. 삼항 연산자로 if문을 통합할 수 있겠다.

- 두 변수 r, c를 half와 비교하여 4가지 중 하나를 고르는 건 통합이 어려울 것 같다.

 

코드

#include <cstdio>
#include <cmath>

int prevSearchCount(int n, int r, int c) {
	if (n == 0)	return 0;

	int half = std::pow(2, n - 1), m = 0;

	if (c >= half && r < half)	m = 1;
	if (c < half && r >= half)	m = 2;
	if (c >= half && r >= half)	m = 3;

	r -= (r < half) ? 0 : half;
	c -= (c < half) ? 0 : half;

	return m * half * half + prevSearchCount(n - 1, r, c);
}

int main() {
	int n, r, c;
	scanf("%d %d %d", &n, &r, &c);
	printf("%d", prevSearchCount(n, r, c));
}

1평면인 경우 그대로기에, 아예 삭제했다.

나는 중괄호를 살리는 편이지만, 코드 길이를 줄이기 위해 한 번 지워봤다.

 

결과

이번에도 문제 없음.

---

가장 효율적인 코드

https://www.acmicpc.net/source/31017326

cgiosy님의 코드. 정말 싫어하는 코드 타입이지만, 볼만한 부분이 있어 가져왔다.

 

내 코드와 비교

- 나는 재귀함수로, 이 분은 for문 반복문으로 구현하셨다. 정확히는 비트(2진수)를 이용하셨다.

- 문제의 n, r, c를 각각 N, y, x에 받으셨다.

- 정답은 z * 4 | x >> N & 1 | y * 2 >> N & 2;로 구하셨다. 비트 연산인데, 자세히 살펴보자.

- ex) N = 2, y = 3, x = 1일 경우

- y, x, 1, 2를 8비트로 풀어쓰면, 00000011, 00000001, 00000001, 00000010이다.

 

첫 번째 루프 (N = 2)

1. x를 2만큼 >> 시프트한다. (00000000)

2. 이를 1과 & 연산한다. (00000000 & 00000001 = 00000000)

3. y도 같은 방법으로 연산한다. y * 2 = 6, (00000110 >> 2 = 00000001, 00000001 & 00000010 = 00000000)

4. z는 처음 불려졌으니 0, z * 4 = 0.

5. 셋 모두 0이기에, 비트 OR 연산 ( | )을 해도 0이다.

 

두 번째 루프 (N = 1)

1. x를 1만큼 시프트한다. (00000000)

2. 이를 1과 & 연산한다. (00000000 & 00000001 = 00000000)

3. y도 같은 방법으로 연산한다. y * 2 = 6, (00000110 >> 1 = 00000011, 00000011 & 00000010 = 00000010)

4. z * 4 = 0.

5. y = 2로 살아남았다. | 연산을 하면 z = 2다. (00000010)

 

세 번째 루프 (N = 0)

1. x를 0만큼 시프트한다. (00000001)

2. 이를 1과 & 연산한다. (00000001 & 00000001 = 00000001)

3. y도 같은 방법으로 연산한다. y * 2 = 6, (00000110 >> 0  = 00000110, 00000110 & 00000010 = 00000010)

4. z * 4 = 8 (00001000)

5. 비트 OR 연산을 하면 z = 00001011, 즉 11이다.

 

비트 단위 연산이 들어가 어려워보이지만, 실제론 벡터로 생각하면 편하다. 각 반복(재귀)에서 사각형은 1/4로 줄어들며, 해당 사각형 내에서 또다시 연산한다. 2진수는 각 비트가 오른쪽 끝부터 2^0, 2^1, 2^2... 에 해당하므로, 이 문제를 풀기에 적합하다.

간단히 말하면, 내가 한 것처럼 이전까지 탐색한 수를 합쳐갈 뿐이다.

---

강평

문제 자체는 재귀의 정석이며 쉬운 문제. 하지만 비트 연산에 대한 이해를, 그리고 응용법을 배울 수 있었다.