백준 #1074 Z

이번 문제는 자기 복제 개념이 들어가 있는 문제입니다.  큰 모양에서도 Z를 이루고, 작은 모양에서도 Z를 이루는 형태로 배열을 채울 때, 주어진 행과 열에 어떤 숫자가 있는지 알아내는 문제입니다.  난이도는 Silver I입니다.

 

2x2에서의 Z

위의 그림과 같이 2x2라면 Z 모양대로 숫자를 배치합니다.  그런데 배열 갯수가 늘어나면,

8x8에서의 Z

과 같이 복잡한 형태가 됩니다.  여기서 주어진 칸의 숫자를 알아내면 됩니다.

 

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

1074번: Z

 

재귀 호출을 이용해서 배열을 채우는 것이 가장 간단한 해답이 될겁니다.  N이 15이하의 숫자이니까, 많아보았자 \(2^{30}=1,073,741,824\)가지입니다.  제한시간 2초이니까, 아슬아슬한 시간이 되겠네요.

 

전 재귀호출을 이용하지 않고 풀었습니다.  (r, c)가 현재의 사각형에서 어느부분에 있는지 검사해서 풀었습니다.  예를 들어서 8x8 배열에서 (6, 3) 이었다면, 다음과 같이 됩니다.

 

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;
}