[백준 1074] Z

www.acmicpc.net/problem/1074

1074번: Z

재귀함수를 사용하는 문제이다. 재귀함수는 아무리 풀어도 익숙해지지가 않는듯하다

사실 이 문제는 재귀함수를 따로 정의하기 보다 while문 돌리는게 편했다.

 

1. 재귀함수 사용

기저 조건은 한 변의 길이가 2인 정사각형일때이다.

cnt의 초기값을 0으로 설정하여 기저 조건에 도달할 때마다 4씩 더해준다.

 

재귀함수 내 재귀함수 호출은 z모양으로 발생한다.

 

#include <stdio.h>

using namespace std;

int n, r, c, cnt;

void fillZ(int len, int row, int col)
{
  if (len == 2)
  {

    for (int i = 0; i < 2; i++)
    {
      for (int j = 0; j < 2; j++)
      {
        if (row + i == r && col + j == c)
        {
          printf("%d\n", cnt);
          return;
        }
        cnt++;
      }
    }
    return;
  }

  len = len / 2;
  fillZ(len, row, col);
  fillZ(len, row, col + len);
  fillZ(len, row + len, col);
  fillZ(len, row + len, col + len);
}
int main(void)
{

  scanf("%d%d%d", &n, &r, &c);

  fillZ(1 << n, 0, 0);

  return 0;
}

 

2. while문 사용 

전체 길이 len = 1<<n에서 r과 c의 위치를 찾는다. 

len의 중간지점인 mid를 중심으로 r과 c를 재조정하고 cnt도 더해준다.

1, 2, 3, 4 순으로 확인하며 1의 경우 어떠한 값도 변화하지 않고 총 길이만 변화시킨다.

 

#include <stdio.h>

using namespace std;

int n, r, c, cnt;

int main(void)
{
  scanf("%d%d%d", &n, &r, &c);

  int len = 1 << n;

  while (len > 1)
  {
    int mid = len / 2;
    if (r < mid && c >= mid)
    {
      c -= mid;
      cnt += mid * mid;
    }
    else if (r >= mid && c < mid)
    {
      r -= mid;
      cnt += mid * mid * 2;
    }
    else if (r >= mid && c >= mid)
    {
      r -= mid;
      c -= mid;
      cnt += mid * mid * 3;
    }
    len = mid;
  }

  printf("%d\n", cnt);

  return 0;
}