백준 #1074 Z
이번 문제는 자기 복제 개념이 들어가 있는 문제입니다. 큰 모양에서도 Z를 이루고, 작은 모양에서도 Z를 이루는 형태로 배열을 채울 때, 주어진 행과 열에 어떤 숫자가 있는지 알아내는 문제입니다. 난이도는 Silver I입니다.
위의 그림과 같이 2x2라면 Z 모양대로 숫자를 배치합니다. 그런데 배열 갯수가 늘어나면,
과 같이 복잡한 형태가 됩니다. 여기서 주어진 칸의 숫자를 알아내면 됩니다.
https://www.acmicpc.net/problem/1074
1074번: Z
한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r,
www.acmicpc.net
재귀 호출을 이용해서 배열을 채우는 것이 가장 간단한 해답이 될겁니다. N이 15이하의 숫자이니까, 많아보았자 \(2^{30}=1,073,741,824\)가지입니다. 제한시간 2초이니까, 아슬아슬한 시간이 되겠네요.
전 재귀호출을 이용하지 않고 풀었습니다. (r, c)가 현재의 사각형에서 어느부분에 있는지 검사해서 풀었습니다. 예를 들어서 8x8 배열에서 (6, 3) 이었다면, 다음과 같이 됩니다.
r, c 값을 계속 2씩 나누어가면서 해당 칸을 얻습니다. 그러면서 숫자를 키워나가면 됩니다.
제가 짠 소스입니다. 소스는 참고용으로 봐주세요.
//----------------------------------------------------------------------------------------
// baekjoon #1074 - Z
// - by Aubrey Choi
// - created at 2019-07-03
//----------------------------------------------------------------------------------------
#include <stdio.h>
int main()
{
int n, r, c, v = 0;
scanf("%d%d%d", &n, &r, &c);
for(int s = 0; r || c; s += 2, r>>=1, c>>=1)
{
v |= ((c & 1) + ((r & 1) << 1)) << s;
}
printf("%d\n", v);
return 0;
}