문제
HCPC 2021에 참석한 $N \times N$명의 사람들이 의자가 정사각형 형태로 배치된 대회장에서 대회를 한다. 모든 의자에는 서로 다른 추첨번호가 적혀있으며 HCPC 2021의 마지막에는 아래에 설명된 규칙에 따라 특별상을 받을 사람 한 명을 정한다.
- 특별상을 받을 수 있는 사람이 한 명이라면, 그 사람이 뽑힌다.
- 그렇지 않은 경우, 대회장을 같은 크기의 정사각형 네 개로 나누어 각 구역에서 이 규칙을 재귀적으로 적용해서 구역마다 한 명씩 총 네 명을 뽑는다.
- 뽑힌 네 명 중 의자에 적힌 추첨번호가 두 번째로 작은 사람이 뽑힌다.
HCPC 2021에 참가한 지원이는 자신의 실력이 부족해서 수상권이 아니라고 생각하였고, 실력과 무관하게 받을 수 있는 특별상을 노리고 있다.
아래 예시를 참고하자.
위와 같은 의자 배열이 있다고 가정하자. 이를 네 개의 구역으로 나누면 아래와 같다.
나누어진 구역의 왼쪽 위 구역을 다시 네 개의 구역으로 나누면 아래와 같다.
여기에서 추첨번호가 두 번째로 낮은 사람을 고르면 아래와 같다.
이와 같은 작업을 모든 영역에 대해 실행하면 아래와 같다.
따라서 특별상을 받는 추첨번호는 아래와 같다.
입력
첫 번째 줄에는 정수 $N$이 주어진다. (단, $N = 2^m$, $0 \le m \le 10$, $m$은 정수)
두 번째 줄부터 $N$개 줄의 $i$번째 줄에는 $i$번째 줄에 있는 의자에 적힌 추첨번호가 주어진다. 각 줄에는 $N$개의 추첨번호가 공백으로 구분되어 주어진다.
추첨번호는 $2^{31}$ 보다 작은 음이 아닌 정수이고, 모든 추첨번호는 서로 다름이 보장된다.
출력
지원이가 HCPC 2021에서 경품을 받기 위해 앉아야 하는 의자에 적힌 추첨번호를 출력한다.
예제 입력 1
2
2 0
3 1
예제 출력 1
1
예제 입력 2
4
15 7 13 5
4 2 1 9
0 10 8 12
3 11 14 6
예제 출력 2
4
풀이
분할정복의 기본 형태이다. 정사각형 형태이기에 4사분면으로 나누어 생각해보면 된다. 사분면에서 두번째로 낮은 추첨번호를 가진 사람이 당첨되는식으로만 설계하면 된다. 정렬 함수를 사용해 두번째로 작은 값을 리턴한다.
import java.util.*;
import java.io.*;
public class Main{
public static int[][] nums; // 추첨 번호 배열
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
nums = new int[N][N];
for(int i = 0; i < N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++)
nums[i][j] = Integer.parseInt(st.nextToken());
}
System.out.print(whoGotPrize(0, 0, N));
}
// 상을 누가 받는지 반환하는 함수
public static int whoGotPrize(int x, int y, int size){
// 사이즈가 1이라면 본인을 반환한다.
if(size == 1)
return nums[y][x];
// 사이즈가 1이 아니라면 4사분면으로 분할하며 각 리턴값들을 모은다.
int[] candis = {whoGotPrize(x, y, size/2),
whoGotPrize(x, y+size/2, size/2),
whoGotPrize(x+size/2, y, size/2),
whoGotPrize(x+size/2, y+size/2, size/2)};
// 리턴값 배열을 정렬하여 두번째로 작은 값을 최종 반환한다.
Arrays.sort(candis);
return candis[1];
}
}
'Algorithm > Problems' 카테고리의 다른 글
[JAVA]평범한 배낭(Baekjoon) (0) | 2023.03.21 |
---|---|
[JAVA]별 찍기 - 11(Baekjoon) (0) | 2023.03.21 |
[JAVA]두 수의 합(Baekjoon) (0) | 2023.02.24 |
[JAVA]색종이(Baekjoon) (0) | 2023.02.24 |
[JAVA]3진법 뒤집기(Programmers) (0) | 2023.02.20 |