C++ / 백준 / 1074 / Z

문제

 

https://www.acmicpc.net/problem/1074

1074번: Z

문제풀이

 

왼쪽 위를 1면, 오른쪽 위를 2면, 왼쪽 아래를 3면, 오른쪽 아래를 4면으로 둔다고 가정한다.

면을 계속 나누면서 해당 면의 최솟값을 더해 값을 구했다.

 

N값을 입력받으면 시프트 연산을 통해 N을 2^N으로 바꾼다.

그다음 함수에서 N을 반으로 나누고 시작한다. (N을 가로 or 세로로 두어 y와 x의 위치를 비교하기 위함)

4면이 있기 때문에 네 가지 조건을 통해 어느 면에 속하는지 판별한다.

 

y, x 가 N보다 작으면 1면, y는 N보다 작고 x는 N이상이면 2면....

1면이면 더할 필요 없으므로 그대로

2면이면 2면의 가장 작은 수는 N*N이므로 N*N를

3면이면 3면의 가장 작은 수는 N*N*2이므로 N*N*2를

4면이면 4면의 가장 작은 수는 N*N*3이므로 N*N*3을 한다.

(입력받은 N이 2일 경우, 함수의 N은 4를 입력받고 2부터 시작한다. 2면이면 최소 4, 3면이면 8, 4면이면 12부터 시작이다)

 

최솟값을 계속해서 더해 값을 찾을 것이므로 N이상인 y 또는 x의 값을 N만큼 빼서 다시 함수를 실행한다.

 

N이 2일 때의 표이다. 여기서 (2,1)인 9의 값을 구해볼 것이다.

그림 1)

함수에는 1<<2 값인 4가 들어온다.

들어오자마자 4/2를 하여 N은 2가 된다.

y=2 >= 2, x=1 < 2 이므로 3면에 해당된다.

3면의 최솟값은 2 * 2 * 2인 8이 된다.

그다음 (N, y-N, x)인 Z(2, 0, 1)를 실행한다.

 

그림 2)

함수에는 2가 들어오고 2/2를 하여 N은 1이 된다.

y=0 < 1, x=1 >= 1 이므로 2면에 해당된다.

2면의 최솟값은 1 * 1이 된다. (누적은 8 + 1)

그다음 (N, y, x-N)인 Z(1, 0, 0)을 실행한다.

N은 1이므로 return 0을 한다.

 

최종 답은 8 + 1 인 9가 된다.

 

 

코드

#include <iostream>
using namespace std;

int Z(int N, int y, int x) {
	int val(0);
	if (N == 1) return 0;
	N /= 2;
	if (y < N && x < N) {
		val += Z(N, y, x);
	}
	else if (y < N && x >= N) {
		val = N * N;
		val += Z(N, y, x - N);
	}
	else if (y >= N && x < N) {
		val = N * N * 2;
		val += Z(N, y - N, x);
	}
	else if (y >= N && x >= N) {
		val = N * N * 3;
		val += Z(N, y - N, x - N);
	}
	return val;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), r(0), c(0);
	cin >> N >> r >> c;
	
	cout << Z(1 << N, r, c);	
}