[BOJ] 1074번: Z

2022. 3. 23. 23:42· BOJ 백준/분할정복
목차
  1. 문제
  2. 입력
  3. 출력
  4. 풀이
  5. 코드
  6. 결과
728x90
반응형

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

 

1074번: Z

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을

www.acmicpc.net

문제

한수는 크기가 2N× 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

 


풀이

📌 분할정복 + 재귀

배열을 4등분으로 나누고 원하는 좌표의 위치를 판단하여 해당 사분면으로 이동한다. 이를 재귀 함수를 이용하여 반복하다 보면 좌표의 위치를 발견할 수 있다. 

 

코드

#include <iostream>
using namespace std;

int n, c, r;
int ans = 0;
int s; 

void visit(int x, int y, int a) {
  if (x == r && y == c) {
    cout << ans << "\n";
    return;
  }

  if(x+a/2 > r && y+a/2 > c) {
    visit(x, y, a/2);  // 1사분면
  }
  else if(x+a/2 > r && y+a/2 <= c) {
    ans += (a/2)*(a/2);
    visit(x, y+a/2, a/2);  // 2사분면
  }
  else if(x+a/2 <= r && y+a/2 > c) {
    ans += (a/2)*(a/2)*2;
    visit(x+a/2, y, a/2);  // 3사분면
  }
  else {
    ans += (a/2)*(a/2)*3;
    visit(x+a/2, y+a/2, a/2);  // 4사분면
  }

  return;

}

int main() {
  int n;
  cin >> n >> r >> c;
  s = 1 << n;  // 1을 왼쪽으로 n비트만큼 이동 (2^n)
  visit(0, 0, s);
  return 0;
}

결과

728x90
반응형

'BOJ 백준 > 분할정복' 카테고리의 다른 글

[BOJ] 1992번: 쿼드트리  (0) 2022.03.30
[BOJ] 1780번: 종이의 개수  (0) 2022.03.28
[BOJ] 2630번: 색종이 만들기  (0) 2022.03.14
  1. 문제
  2. 입력
  3. 출력
  4. 풀이
  5. 코드
  6. 결과
'BOJ 백준/분할정복' 카테고리의 다른 글
  • [BOJ] 1992번: 쿼드트리
  • [BOJ] 1780번: 종이의 개수
  • [BOJ] 2630번: 색종이 만들기
코블리_vv
코블리_vv
코블리_vv
코딩 놀이터
코블리_vv
전체
오늘
어제
  • 분류 전체보기 (67)
    • CS 노트 (1)
    • 대외활동 (0)
      • 창업 동아리 (0)
    • AWS (0)
      • AWS Academy Cloud Architect.. (0)
      • AWS Lab (0)
    • 웹 개발 노트 (3)
      • 웹 프로젝트 (0)
      • 스프링 인 액션 (0)
      • 스프링 입문을 위한 자바 객체 지향의 원리와 이해 (0)
    • ORACLE (0)
    • TOPCIT (2)
      • M1 소프트웨어 개발 (2)
      • M2 데이터 이해와 활용 (0)
    • 캡스톤 (5)
    • BOJ 백준 (53)
      • 브루트포스 (1)
      • 정렬 (6)
      • 이분탐색 (5)
      • 맵 (2)
      • 다이나믹 프로그래밍 (11)
      • 수학 (5)
      • 그리디 (3)
      • 분할정복 (4)
      • DFS (3)
      • BFS (6)
      • 그래프 (4)
      • 자료구조 (1)
      • 백트래킹 (2)
    • 코딩 테스트 (0)
      • 코드트리 (0)
    • 대회 (0)
    • Spring Boot (3)
      • JPA (3)

블로그 메뉴

  • 홈
  • 태그
  • 알고리즘
  • BOJ 백준
  • 방명록

공지사항

인기 글

태그

  • 웹개발
  • computer security
  • 이분탐색
  • 파이썬 backtrader
  • 백트래킹
  • 그리디 알고리즘
  • n과m
  • 백준 n과m
  • 재귀
  • 1676
  • dfs
  • 분할정복
  • 투자 전략
  • 다이나믹 프로그래밍
  • binary search
  • dp
  • 우선순위 큐
  • 플로이드 와샬
  • 너비우선탐색
  • backtrader
  • spring
  • 다이나믹프로그래밍
  • java
  • BFS
  • 컴퓨터 보안
  • 암호학
  • 투자
  • 백준 토마토
  • 시스템 트레이딩
  • 스프링인액션

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
코블리_vv
[BOJ] 1074번: Z
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.