알고리즘 스터디(2) - 1074번: Z

🤍 실버1 - 1074번: Z

🔻 C언어

#include <stdio.h>
#include <math.h>

int N, r, c, count;

void Z(int x, int y, int square);
// Z 함수를 미리 선언! 

int main(void) {
  scanf("%d %d %d", &N, &r, &c);
  Z(0, 0, pow(2, N)); // 2의 N제곱 표현
  // 입력값을 받고, Z 함수를 호출
  return 0;
}

void Z(int x, int y, int square) {
  if (square == 1) {
    if (x == r && y == c) {
      printf("%d\n", count);
      // square가 1이고, 현재 좌표가 찾는 좌표와 일치할 때 count를 출력
    }
    count++;
    return;
    // square 1이고, 현재 좌표가 찾는 좌표와 일치하지 않을 때 count를 증가시키고 리턴
  }
  
  int nextSquare = square / 2;
  // 현재 size를 반으로 나누어 다음 사이즈를 계산, 계속 2의 지수를 1씩 감소시키기
  
  Z(x, y, nextSquare); // 좌상단
  Z(x, y + nextSquare, nextSquare); // 우상단
  Z(x + nextSquare, y, nextSquare); // 좌하단
  Z(x + nextSquare, y + nextSquare, nextSquare); // 우하단
  // 좌상단, 우상단, 좌하단, 우하단 순서로 Z 함수를 재귀호출!
  
  return;
}

위 코드는 입력받은 N의 값에 따라 배열을 Z자 모양으로 탐색하며 각 칸에 번호를 매기는 함수 Z를 구현한 것이다.

이때, Z 함수 내에서는 현재 좌표와 찾고자 하는 좌표가 일치할 때까지 좌상단, 우상단, 좌하단, 우하단 순서로 재귀호출되며, square가 1일 때 찾고자 하는 좌표와 일치하는지 확인한 후 일치하면 count를 출력!

➡️ 시간초과,, 띠로리

#include <stdio.h>
#include <math.h>

int Z(int N, int r, int c) {
    if (N == 0) return 0;

    int Square = (int)pow(2, N);
    int nextSquare = Square / 2;

    if (r < nextSquare && c < nextSquare) { // 좌상단
        return Z(N - 1, r, c);
    }
    else if (r < nextSquare && c >= nextSquare) { // 우상단
        return nextSquare * nextSquare + Z(N - 1, r, c - nextSquare);
    }
    else if (r >= nextSquare && c < nextSquare) { // 좌하단
        return nextSquare * nextSquare * 2 + Z(N - 1, r - nextSquare, c);
    }
    else {  // 우하단
        return nextSquare * nextSquare * 3 + Z(N - 1, r - nextSquare, c - nextSquare);
    }
}

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

    int count = Z(N, r, c);
    printf("%d\n", count);

    return 0;
}