[Platinum V] 어항 정리 - 23291
성능 요약
메모리: 16096 KB, 시간: 132 ms
분류
구현, 시뮬레이션
문제 설명
마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바닥 위에 놓여져 있다. 어항에는 물고기가 한 마리 이상 들어있다. <그림 1>은 어항 8개가 바닥 위에 놓여있는 상태이며, 칸에 적힌 값은 그 어항에 들어있는 물고기의 수이다. 편의상 어항은 정사각형으로 표현했다.
<그림 1>
어항을 한 번 정리하는 과정은 다음과 같이 이루어져 있다.
먼저, 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 만약, 그러한 어항이 여러개라면 물고기의 수가 최소인 어항 모두에 한 마리씩 넣는다. 위의 예시의 경우 물고기의 수가 가장 적은 어항에는 물고기가 2마리 있고, 그러한 어항은 2개가 있다. 따라서, 2개의 어항에 물고기를 한 마리씩 넣어 <그림 2>와 같아진다.
<그림 2>
이제 어항을 쌓는다. 먼저, 가장 왼쪽에 있는 어항을 그 어항의 오른쪽에 있는 어항의 위에 올려 놓아 <그림 3>이 된다.
<그림 3>
이제, 2개 이상 쌓여있는 어항을 모두 공중 부양시킨 다음, 전체를 시계방향으로 90도 회전시킨다. 이후 공중 부양시킨 어항을 바닥에 있는 어항의 위에 올려놓는다. 바닥의 가장 왼쪽에 있는 어항 위에 공중 부양시킨 어항 중 가장 왼쪽에 있는 어항이 있어야 한다. 이 작업은 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 있을때까지 반복한다.
먼저, <그림 4>와 같이 어항이 놓인 상태가 변하고, 한 번 더 변해서 <그림 5>가 된다.
<그림 4>
<그림 5>
<그림 5>에서 한 번 더 어항을 공중 부양시키는 것은 불가능하다. 그 이유는 <그림 6>과 같이 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 없기 때문이다.
<그림 6>
공중 부양 작업이 모두 끝나면, 어항에 있는 물고기의 수를 조절한다.
모든 인접한 두 어항에 대해서, 물고기 수의 차이를 구한다. 이 차이를 5로 나눈 몫을 d라고 하자. d가 0보다 크면, 두 어항 중 물고기의 수가 많은 곳에 있는 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다. 이 과정은 모든 인접한 칸에 대해서 동시에 발생한다. 이 과정이 완료되면 <그림 7>이 된다.
<그림 7>
이제 다시 어항을 바닥에 일렬로 놓아야 한다. 가장 왼쪽에 있는 어항부터, 그리고 아래에 있는 어항부터 가장 위에 있는 어항까지 순서대로 바닥에 놓아야 한다. <그림 8>이 바닥에 다시 일렬로 놓은 상태이다.
<그림 8>
다시 공중 부양 작업을 해야 한다. 이번에는 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전 시킨 다음, 오른쪽 N/2개의 위에 놓아야 한다. 이 작업은 두 번 반복해야한다. 두 번 반복하면 바닥에 있는 어항의 수는 N/4개가 된다. <그림 9>는 이 작업을 1번 했을 때, <그림 10>은 다시 한 번 더 했을 때이다.
<그림 9>
<그림 10>
여기서 다시 위에서 한 물고기 조절 작업을 수행하고, 바닥에 일렬로 놓는 작업을 수행한다. <그림 10>에서 조절 작업을 마친 결과는 <그림 11>이 되고, 여기서 다시 바닥에 일렬로 놓는 작업을 수행하면 <그림 12>가 된다.
<그림 11>
<그림 12>
어항의 수 N, 각 어항에 들어있는 물고기의 수가 주어진다. 물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면 어항을 몇 번 정리해야하는지 구해보자.
입력
첫째 줄에 N, K가 주어진다. 둘째에는 어항에 들어있는 물고기의 수가 가장 왼쪽에 있는 어항부터 순서대로 주어진다.
출력
물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면 어항을 몇 번 정리해야하는지 출력한다.
문제 풀이
해당 문제는 시뮬레이션 문제로 주어진 조건들을 충족하도록 설계해야 하는 문제다.
물고기 수의 최대/최소인 어항의 차이가 K이하일 때 까지 반복하면 된다.
사실상 노가다가 매우 심한 문제라서 필자는 선호하지 않는 문제의 유형이다..
- 물고기가 최소인 어항에 물고기 추가
- 어항 쌓기
- 물고기 수 조절
- 어항 일렬로 배치
- 어항 접기
- 물고기 수 조절
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int n, k;
static int[][] aquarium;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
initialize();
int count = 0;
while (maxDifferenceExceeds(k)) {
count++;
increaseFish();
firstFold();
spreadAlgae();
unfold();
secondFold();
spreadAlgae();
unfold();
}
System.out.println(count);
}
public static boolean maxDifferenceExceeds(int k) {
int minFish = Integer.MAX_VALUE;
int maxFish = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
minFish = Math.min(minFish, aquarium[i][0]);
maxFish = Math.max(maxFish, aquarium[i][0]);
}
return maxFish - minFish > k;
}
public static void increaseFish() {
int minFish = Integer.MAX_VALUE;
for (int i = 0; i < n; i++)
minFish = Math.min(minFish, aquarium[i][0]);
for (int i = 0; i < n; i++) {
if (aquarium[i][0] == minFish)
aquarium[i][0]++;
}
}
public static void firstFold() {
int startX = 0;
int vertical = 1;
int horizontal = 1;
while (startX + vertical + horizontal <= n) {
for (int i = vertical - 1; i >= 0; i--) {
for (int j = 0; j < horizontal; j++) {
int newX = startX + vertical + j;
int newY = vertical - i;
aquarium[newX][newY] = aquarium[startX + i][j];
aquarium[startX + i][j] = 0;
}
}
startX += vertical;
if (vertical == horizontal) horizontal++;
else vertical++;
}
}
public static void spreadAlgae() {
int[][] save = new int[n][25];
boolean[][] visited = new boolean[n][25];
for (int x = 0; x < n; x++) {
for (int y = 0; y < 25; y++) {
visited[x][y] = true;
if (aquarium[x][y] == 0) continue;
for (int dir = 0; dir < 4; dir++) {
int newX = x + dx[dir];
int newY = y + dy[dir];
if (isValid(newX, newY) && !visited[newX][newY] && aquarium[newX][newY] != 0) {
int diff = (aquarium[x][y] - aquarium[newX][newY]) / 5;
if (Math.abs(diff) >= 1) {
save[x][y] -= diff;
save[newX][newY] += diff;
}
}
}
}
}
for (int x = 0; x < n; x++) {
for (int y = 0; y < 25; y++) {
aquarium[x][y] += save[x][y];
}
}
}
public static void unfold() {
int x = 0;
while (aquarium[x][0] == 0) x++;
int index = 0;
int[] save = new int[n];
for (int i = x; i < n; i++) {
for (int j = 0; j < 25; j++) {
if (aquarium[i][j] == 0) break;
save[index++] = aquarium[i][j];
aquarium[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
aquarium[i][0] = save[i];
}
}
public static void secondFold() {
for (int i = 0; i < n / 2; i++) {
aquarium[n - 1 - i][1] = aquarium[i][0];
aquarium[i][0] = 0;
}
for (int i = 0; i < n / 4; i++) {
for (int j = 0; j < 2; j++) {
aquarium[n - 1 - i][3 - j] = aquarium[n / 2 + i][j];
aquarium[n / 2 + i][j] = 0;
}
}
}
static void initialize() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
n = Integer.parseInt(line[0]);
k = Integer.parseInt(line[1]);
aquarium = new int[n][25];
line = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
aquarium[i][0] = Integer.parseInt(line[i]);
}
}
public static boolean isValid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < 25;
}
}
코드 풀이
public class Main {
static int n, k;
static int[][] aquarium;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};n,k: 수조의 크기와 최대 차이를 나타내는 변수aquarium: 수조 내의 물고기와 해조류 정보를 저장하는 배열dx,dy: 이동 방향을 나타내는 배열
public static void main(String[] args) throws IOException {
initialize();
int count = 0;initialize: 입력을 받아 프로그램이 작업을 수행하기 위한 초기 설정을 완료하는 함수count: 작업 횟수를 세는 변수while (maxDifferenceExceeds(k)) { count++; increaseFish(); firstFold(); spreadAlgae(); unfold(); secondFold(); spreadAlgae(); unfold(); } System.out.println(count); }maxDifferenceExceeds(k)메서드를 사용해 어항 내 물고기의 최대 최소 차이가 k보다 큰지 확인한다.- 조건이 충족된다면, 어항을 조작하고, 조작 횟수를 count 변수를 증가시킨다.
- 조작이 끝나면 조작 횟수를 출력한다.
increaseFish(): 물고기 증가 함수 호출firstFold(): 첫 번째 접기 작업 수행spreadAlgae(): 해조류 확산 함수 호출unfold(): 배열 펴기 작업 수행secondFold(): 두 번째 접기 작업 수행spreadAlgae(): 해조류 확산 함수 호출unfold(): 배열 펴기 작업 수행
System.out.println(count);
}
public static boolean maxDifferenceExceeds(int k) {
int minFish = Integer.MAX_VALUE;
int maxFish = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
minFish = Math.min(minFish, aquarium[i][0]);
maxFish = Math.max(maxFish, aquarium[i][0]);
}
return maxFish - minFish > k;
}maxDifferenceExceeds(): 물고기의 최대 차이가 주어진 값 k를 초과하는지 확인하는 함수- for문은 수조 내의 물고기 중 최소값과 최대값을 찾아준다.
- 최대 차이가 k를 초과하면 true 반환, 아니면 false 반환한다.
public static void increaseFish() { int minFish = Integer.MAX_VALUE; for (int i = 0; i < n; i++) minFish = Math.min(minFish, aquarium[i][0]); for (int i = 0; i < n; i++) { if (aquarium[i][0] == minFish) aquarium[i][0]++; } }- minFish를 찾아서 그 위치에 있는 물고기 수를 증가시킨다.
increaseFish(): 물고기 증가 함수Math.min을 사용해서 수조 내 물고기 중 최소값을 찾는다.- 어항 내 가장 적은 물고기 수를 가진 곳에 물고기를 추가한다.
public static void firstFold() { int startX = 0; int vertical = 1; int horizontal = 1; while (startX + vertical + horizontal <= n) { for (int i = vertical - 1; i >= 0; i--) { for (int j = 0; j < horizontal; j++) { int newX = startX + vertical + j; int newY = vertical - i; aquarium[newX][newY] = aquarium[startX + i][j]; aquarium[startX + i][j] = 0; } } startX += vertical; if (vertical == horizontal) horizontal++; else vertical++; } }firstFold(): 첫 번째로 배열을 접는 작업 수행하는 함수- 배열을 vertical과 horizontal 두 개의 변수를 사용하여 접는다.
startX: 현재 접는 위치를 나타내며, 초기에 0으로 설정된다.vertical방향으로 배열을horizontal방향으로 이동하면서 요소를 옮긴다.horizontal방향으로 배열을vertical방향으로 이동하면서 요소를 옮긴다.- 이러한 작업을 반복하면서 배열을 계속해서 접는다.
public static void spreadAlgae() { int[][] save = new int[n][25]; boolean[][] visited = new boolean[n][25]; for (int x = 0; x < n; x++) { for (int y = 0; y < 25; y++) { visited[x][y] = true; if (aquarium[x][y] == 0) continue; for (int dir = 0; dir < 4; dir++) { int newX = x + dx[dir]; int newY = y + dy[dir]; if (isValid(newX, newY) && !visited[newX][newY] && aquarium[newX][newY] != 0) { int diff = (aquarium[x][y] - aquarium[newX][newY]) / 5; if (Math.abs(diff) >= 1) { save[x][y] -= diff; save[newX][newY] += diff; } } } } } for (int x = 0; x < n; x++) { for (int y = 0; y < 25; y++) { aquarium[x][y] += save[x][y]; } } }spreadAlgae(): 해조류 확산 함수- 모든 좌표에 대해 해조류 확산 및 상호작용을 계산하는 반복문
- 확산 및 상호작용 결과를 반영하는 반복문
- 정리하면, 어항을 세로와 가로 방향으로 반복적으로 접고, 데이터를 이동시킨다.
public static void unfold() { int x = 0; while (aquarium[x][0] == 0) x++; int index = 0; int[] save = new int[n]; for (int i = x; i < n; i++) { for (int j = 0; j < 25; j++) { if (aquarium[i][j] == 0) break; save[index++] = aquarium[i][j]; aquarium[i][j] = 0; } } for (int i = 0; i < n; i++) { aquarium[i][0] = save[i]; } }unfold()배열을 펴는 작업 수행하는 함수- 배열의 첫 번째 열에서 0이 아닌 값이 나오는 위치를 찾는 반복문
- 배열을 펴면서 값을 저장하고 초기화하는 반복문
- 저장된 값으로 배열을 초기화
- 가장 위에서부터 물고기를 차례대로 저장하고, 데이터를 펼쳐진 상태로 업데이트한다.
public static void secondFold() { for (int i = 0; i < n / 2; i++) { aquarium[n - 1 - i][1] = aquarium[i][0]; aquarium[i][0] = 0; } for (int i = 0; i < n / 4; i++) { for (int j = 0; j < 2; j++) { aquarium[n - 1 - i][3 - j] = aquarium[n / 2 + i][j]; aquarium[n / 2 + i][j] = 0; } } }secondFold()두 번째로 배열을 접는 작업을 수행하는 함수- 어항의 하단에서 상단으로 물고기를 이동시키고, 데이터를 업데이트한다.
static void initialize() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line = br.readLine().split(" "); n = Integer.parseInt(line[0]); k = Integer.parseInt(line[1]); aquarium = new int[n][25]; line = br.readLine().split(" "); for (int i = 0; i < n; i++) { aquarium[i][0] = Integer.parseInt(line[i]); } } public static boolean isValid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < 25; } }initialize(): 입력을 받아 프로그램이 작업을 수행하기 위한 초기 설정을 완료하는 함수
'백준 문제풀이' 카테고리의 다른 글
| [Baekjoon 1987] 알파벳 - JAVA (0) | 2023.09.10 |
|---|---|
| [Baekjoon 9527] 1의 개수 세기 - JAVA (0) | 2023.09.05 |
| [Baekjoon 8120] Coding of Permutations - JAVA (0) | 2023.09.01 |
| [Baekjoon 20921] 그렇고 그런 사이 - JAVA (0) | 2023.08.29 |
| [Baekjoon 4307] 개미 - JAVA (0) | 2023.08.28 |
