[백준 문제 C++] 1074 Z

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

1074번: Z

위와 같이 Z 모양으로 순회하며 확장이 된다. 사실 N값은 없어도 되고,

Row, Column 값으로 정답을 구할 수 있다.

위의 패턴을 분석해보면 아래와 같은 모양이 됨을 알 수가 있었다.

(실수로 숫자가 0이 아닌 1로 시작하였다..)

위의 문제에서 Row와 Column은 0으로 시작된다.

[0, 0] = 1

[0, 1] = 2

[1, 0] = 3

[1, 1] = 4

이런식의 값을 갖게 된다.

 

자 여기서 r = 2, c = 2를 찾아보면?

정답은 13이 된다. (실제 답은 12가 나와야 됩니다 실수로 1부터 시작했네유 :D )

 

이번엔 계산으로 구해보면 "r과 c는 2의 몇 제곱수에 걸쳐있느냐?" 를 찾으면 된다.

이것으로 r과 c의 경계를 알 수 있고 미리 계산이 가능해진다.

(대신 인덱스가 0부터 시작하기 때문에 r == 2^x 인 경우도 경계를 넘는것으로 인정해주어야 한다.)

 

아래의 그림을 확인해보자. 뭔가 떠오르지 않을까!

 

위의 초록 경계 구역을 걸러낼 수 있게된다. 저 부분은 미리 더해주고 복잡하니깐 없는 것으로 취급해도 된다.

 

(인덱스가 0부터 시작하기 때문에 r == 2^x 인 경우도 경계를 넘는것으로 인정해주어야 한다.)

row = 2로 4 x 4의 구역에 들어간다. 이전 구역 2 x 2 부분은 2번 넘어왔다는 것을 알 수 있다.

col = 2로 4 x 4의 구역에 들어간다. 이전 구역 2 x 2 부분을 1번 넘어왔다.

 

즉 위의

         row와 col 은 4 x 4 로 4의 경계에 있기 때문에

                          4 / 2 = 2 가 이전 경계가 된다.

          (row 2개 구역) + (col 1개 구역)

             ( 2 x 2 x 2 ) + ( 2 x 2 )

           를 계산해주고 치워버려도 된다.

어차피 패턴은 똑같기 때문이다. 남는 것은 아래와 같다.

 남기기 위해 row와 col 값을 변경해준다. 계산이 끝난 부분은 필요 없기 때문이다.

  row : 미리 계산 된 곳은 빼준다.   row = row(2) - 2^2 / 2 = 0

  col  : 미리 계산 된 곳은 빼준다.   col = col(2) - 2^2 / 2 = 0

row = 0, col = 0 으로 이제 위의 입장에 봤을 때 0, 0이 정답이다. (원래는 12가 정답)

 

만약에 남은 인덱스가 0, 0 이 아니라 2, 4 등의 다른 숫자가 나오면 해당 부분도 계속 2의 제곱 수로

경계를 걸러주며 갯수는 결과에 더해주고, 해당 구역은 제거해 주면서 반복하면 된다.

 

중요한 것은

(row, col 인덱스가 0부터 시작하기 때문에 r == 2^x 인 경우도 경계를 넘는것으로 인정해준다.)

row가 경계를 넘게 되면 2개의 구역을 넘게 된다. 2개의 구역에 대해 더해주기.

col은 왼편의 1개의 구역만을 넘기때문에 1개의 구역에 대해서만 더해주면 된다.

 

#include <iostream>

using namespace std;

int main()
{
	int n, r, c;
	int result = 0;

	cin >> n >> r >> c;

	while (r > 0)
	{
		int size = 2;
		while (size <= r)
		{
			size *= 2;
		}

		size /= 2;
		result += size * size * 2;
		r -= size;
	}

	while (c > 0)
	{
		int size = 2;
		while (size <= c)
		{
			size *= 2;
		}

		size /= 2;
		result += size * size;
		c -= size;
	}

	cout << result << endl;
}