이 영역을 누르면 첫 페이지로 이동
hoonDEV 블로그의 첫 페이지로 이동

hoonDEV

페이지 맨 위로 올라가기

hoonDEV

BOJ 1074 - Z 문제풀이

  • 2020.04.18 21:52
  • 알고리즘/문제풀이

문제를 읽고 이해하기

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

재정의와 추상화

전형적인 분할 정복 문제이지만, 그 구현부가 조금 독특하다는 점이 특징이다.

  • 주어진 길이가 2일 때까지 계속 4등분한다. 4등분할 때 순서는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서(Z)를 꼭 지켜주어야 한다.
  • 주어진 길이가 2일 경우, 아까 언급한 순서를 지켜 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 방문한다. 방문할 때마다 cnt 값을 1씩 증가시키고, 만약 좌표가 (r, c)일 경우 진행을 중단한다.

코드 작성

#include <iostream>
#include <cmath>
using namespace std;

typedef struct {
    int y, x;
} Position;

Position pos[4] = {
        {0, 0},
        {0, 1},
        {1, 0},
        {1, 1}
};

int n, r, c, cnt;

bool divide_and_conquer(int y, int x, int length) {
    if (length != 2) {
        if (divide_and_conquer(y, x, length / 2)) return true;
        if (divide_and_conquer(y, x + length / 2, length / 2)) return true;
        if (divide_and_conquer(y + length / 2, x, length / 2)) return true;
        if (divide_and_conquer(y + length / 2, x + length / 2, length / 2)) return true;
        return false;
    }
    for (auto & p : pos) {
        int now_y = y + p.y;
        int now_x = x + p.x;
        cnt++;
        if (now_y == r && now_x == c) return true;
    }
    return false;
}

int main() {
    cin >> n >> r >> c;
    divide_and_conquer(0, 0, pow(2, n));
    cout << cnt - 1;
    return 0;
}

'알고리즘 > 문제풀이' 카테고리의 다른 글

BOJ 1806 - 부분합 문제풀이  (0) 2020.04.19
BOJ 12015 - 가장 긴 증가하는 부분 수열 2 문제풀이  (0) 2020.04.19
BOJ 7579 - 앱 문제풀이  (0) 2020.04.18
BOJ 12852 - 1로 만들기 2 문제풀이  (0) 2020.04.18
BOJ 1520 - 내리막 길 문제풀이  (0) 2020.04.18

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • BOJ 1806 - 부분합 문제풀이

    BOJ 1806 - 부분합 문제풀이

    2020.04.19
  • BOJ 12015 - 가장 긴 증가하는 부분 수열 2 문제풀이

    BOJ 12015 - 가장 긴 증가하는 부분 수열 2 문제풀이

    2020.04.19
  • BOJ 7579 - 앱 문제풀이

    BOJ 7579 - 앱 문제풀이

    2020.04.18
  • BOJ 12852 - 1로 만들기 2 문제풀이

    BOJ 12852 - 1로 만들기 2 문제풀이

    2020.04.18
다른 글 더 둘러보기

정보

hoonDEV 블로그의 첫 페이지로 이동

hoonDEV

  • hoonDEV의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그

카테고리

  • 분류 전체보기 (91)
    • 일상 (13)
      • 후기 (1)
      • 계획 (11)
    • 공지사항 (1)
    • 알고리즘 (54)
      • 문제풀이 (53)
      • 이론 (1)
    • 공부 (19)
      • React (0)
      • Angular (5)
      • Java (3)
      • C, C++ (3)
      • JavaScript (6)
      • WEB (2)
    • 디자인 (1)
      • UI, UX (1)
    • 개발 (0)
      • boom (0)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • javascript
  • 그리디
  • 문제풀이
  • 이분탐색
  • 백준
  • 알고리즘
  • dp
  • es6

나의 외부 링크

정보

훈개발자의 hoonDEV

hoonDEV

훈개발자

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. © 훈개발자. Designed by Fraccino.

티스토리툴바