[Silver I] Z - 1074
성능 요약
메모리: 13936 KB, 시간: 104 ms
분류
분할 정복, 재귀
제출 일자
2023년 11월 26일 13:37:36
문제 설명
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 22 × 22 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.
입력
첫째 줄에 정수 N, r, c가 주어진다.
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
1. 2^n승에 / 2를 구한 뒤 넓이를 잘 활용해서 풀어야했던 문제
2. 분할 정복, 수학적으로 생각하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int size = (int)Math.pow(2,n);
System.out.println(z(size,r,c));
}
private static int z(int n,int r, int c) {
// n == 0이면 return
if(n == 0) return 0;
// half는 현재 보고 있는 배열의 길이의 절반
int half = (int)Math.pow(2,n-1);
// 1사분면
if(r < half && c < half) return z(n-1,r,c);
// 2사분면에 위치한다면 1사분면에 넓이와 r,c에 위치를 더함
else if(r < half && c >= half) return half * half + z(n-1,r,c - half);
// 3사분면에 위치한다면 1,2사분면에 넓이를 더하고 r,c에 위치를 더 함
else if(r >= half && c < half) return 2 * half * half + z(n-1,r-half,c);
// 4사분면에 위치한다면 1,2,3사분면에 넓이를 더하고 r,c위치를 찾아 더함
else return 3 * half * half + z(n-1,r-half,c-half);
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 1992번 : 쿼드트리 Silver1(실버1) - JAVA[자바] (1) | 2023.11.28 |
---|---|
[백준] 1780번 : 종이의 개수 Silver2(실버2) - JAVA[자바] (1) | 2023.11.27 |
[백준] 9613번 : GCD합 Silver4(실버4) - JAVA[자바] (1) | 2023.11.26 |
[백준] 1850번 : 최대공약수 Silver1(실버1) - JAVA[자바] (1) | 2023.11.26 |
[백준] 1699번 : 제곱수의 합 Silver2(실버2) - JAVA[자바] (1) | 2023.11.25 |