[백준/골드1] 23291. 어항 정리

문제

---

문제

마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 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 이하가 되려면 어항을 몇 번 정리해야하는지 출력한다.

제한

• 4 ≤ N ≤ 100
• N은 4의 배수
• 0 ≤ K ≤ 10
• 1 ≤ 각 어항에 들어있는 물고기의 수 ≤ 10,000

 

풀이

---

접근 방법

• 어항의 길이가 100정도 밖에 안되길래 시간초과는 안 날 것 같아서 그냥 구현 문제라고 생각하고 풀었다.
• 행렬로 풀까 하다가 ArrayList 배열로 풀기로 정했다.

구현할 로직 요약

• 최대 물고기수 - 최소 물고기 수가 K보다 작을 때 까지 반복

1. 최대값과 최소값을 찾는다. 물고기 수가 최소값인 곳에 1을 더함
2. 맨 왼쪽에 있는 어항을 그 다음 어항 위에 올린다.
3. 되는 만큼 굴리기
4. 물고기 조절 작업
5. 펼치기
6. 공중부양 2번
7. 물고기 조절 작업
8. 펼치기

 

각 단계별 설명과 그림

• 초기 상태
  • arr 라는 ArrayList 배열을 선언해서 초기 배열을 저장한다.

 

• step1: 최대값과 최소값을 찾는다. 물고기 수가 최소값인 곳에 1을 더함
  • 반복문을 이용해서 Min과 Max를 찾고 이 차이가 K보다 작으면 while문을 벗어난다.
  • Min값이 여러 개일 수도 있으니까 반복문 다시 돌리면서 Min값을 가진 곳에 +1 해준다.

 

• step2: 맨 왼쪽에 있는 어항을 그 다음 어항 위에 올린다.

• step3: 되는 만큼 굴리기
  • 그림은 두 번 굴렸을 때이다.

• step4: 물고기 조절 작업
  • dx, dy 배열을 이용해서 모든 위치에서 모든 방향을 확인하면서 차이가 얼마나 나는지 확인한다.
  • 이 때 주의할 점은 계산을 두번 하지 않도록 해야 한다.
  • 내가 보고있는 위치만 생각해서 계산해야 한다. 예를 들어 아래 그림에서 4,1을 기준 위치라고 하면 +1 부분만 계산하는 것이다. 그래야지 모든 위치를 확인할 때 중복해서 계산되지 않는다.

• step5: 펼치기
  • 화살표 방향을 따라가면서 일렬로 세운다.

• step6: 공중부양 2번

• step7: 물고기 조절 작업
  • step4랑 같은 함수를 사용한다.

• step8: 펼치기
  • step5와 같은 함수를 사용한다.

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
// [골드1] 어항정리
public class baekjoon_23291 {
	static int N, K;
	static int Min, Max;
	static ArrayList<Integer>[] arr;

	static int[] dx = { 0, 0, -1, 1 }; // 상하좌우
	static int[] dy = { -1, 1, 0, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		arr = new ArrayList[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = new ArrayList<Integer>();
			arr[i].add(Integer.parseInt(st.nextToken()));
		}

		int cnt = 0;
		while (true) {
			// 최대값과 최소값을 찾는다
			Min = Integer.MAX_VALUE;
			Max = 0;
			findMinMax();

			if (Max-Min <= K) {
				break;
			}

			// 1. 최소값인 곳에 1을 더함
			minAddOne();

			// 2. 맨 왼쪽에 있는 어항을 그 다음 어항 위에 올린다.
			firstOnSecond();

			// 3. 되는 만큼 굴리기
			while (true) {
				if (!roll()) { // 굴릴 수 없으면 break;
					break;
				}
			}

			// 4. 물고기 조절 작업
			adjustFishNum();

			// 5. 펼치기
			open();

			// 6. 공중부양 2번
			gongjungFirst();
			gongjungSecond();

			// 7. 물고기 조절 작업
			adjustFishNum();

			// 8. 펼치기
			open();

			cnt++;
		}
		System.out.println(cnt);
	}
	
	// 6. 공중부양 2번
	private static void gongjungSecond() {
		int ref = N / 2 + N / 4;
		for (int j = 1; j >= 0; j--) {
			for (int i = 0; i < N / 4; i++) {
				arr[ref + i].add(arr[ref - 1 - i].get(j));
			}
		}

		for (int i = N / 2; i < ref; i++) {
			arr[i] = new ArrayList<>();
		}

	}

	// 6. 공중부양 1번
	private static void gongjungFirst() {
		for (int i = 0; i < N / 2; i++) {
			arr[N - i - 1].add(arr[i].get(0));
			arr[i] = new ArrayList<>();
		}
	}
	
	// 5. 펼치기
	private static void open() {
		ArrayList<Integer>[] openarr = new ArrayList[N];

		int idx = 0;
		for (int i = 0; i < N; i++) {
			if (arr[i].size() == 0) {
				continue;
			}
			for (int j = 0; j < arr[i].size(); j++) {
				openarr[idx] = new ArrayList<>();
				openarr[idx].add(arr[i].get(j));
				idx++;
			}
		}

		arr = openarr;

	}
	
	// 4. 물고기 조절 작업
	private static void adjustFishNum() {
		ArrayList<Integer>[] calc = new ArrayList[arr.length];
		for (int i = 0; i < arr.length; i++) {
			calc[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].size(); j++) {
				int sum = 0;
				for (int d = 0; d < 4; d++) {
					int nx = i + dx[d];
					int ny = j + dy[d];
					if (nx < 0 || nx >= arr.length || ny < 0 || ny >= arr[nx].size()) {
						continue;
					}

					if (Math.abs(arr[i].get(j) - arr[nx].get(ny)) < 5) {
						continue;
					}

					// 자기 칸 위주로 생각하기
					sum += (arr[nx].get(ny) - arr[i].get(j)) / 5;
				}
				calc[i].add(sum);
			}
		}

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].size(); j++) {
				arr[i].set(j, arr[i].get(j) + calc[i].get(j));
			}
		}
	}

	// 3. 되는 만큼 굴리기
	private static boolean roll() {
		int startIdx = 0; // 굴리기 시작할 인덱스
		int endIdx = 0; // 굴리기 끝나는 인덱스
		int size = 0;

		// 굴리기 시작할 인덱스 찾기
		while (true) {
			if (arr[startIdx].size() != 0) {
				size = arr[startIdx].size();
				break;
			}
			startIdx++;
		}

		// 굴리기 끝낼 인덱스 찾기
		endIdx = startIdx;
		while (true) {
			if (endIdx >= N ||arr[endIdx].size() != size) {
				break;
			}
			endIdx++;
		}

		endIdx--;

		// 못굴리는 경우
		if (endIdx + size >= N) {
			return false;
		}

		// 굴릴 수 있으면?
		for (int i = endIdx; i >= startIdx; i--) {
			for (int j = 0; j < size; j++) {
				arr[endIdx + 1 + j].add(arr[i].get(j));
			}
			arr[i] = new ArrayList<>();
		}
		return true;
	}
	
	// 2. 맨 왼쪽에 있는 어항을 그 다음 어항 위에 올린다.
	private static void firstOnSecond() {
		arr[1].add(arr[0].get(0));
		arr[0] = new ArrayList<>();
	}
	
	// 1. 최소값인 곳에 1을 더함
	private static void minAddOne() {
		for (int i = 0; i < N; i++) {
			if (arr[i].get(0) == Min) {
				arr[i].set(0, Min + 1);
			}
		}
	}

	private static void findMinMax() {
		for (int i = 0; i < N; i++) {
			Max = Math.max(arr[i].get(0), Max);
			Min = Math.min(arr[i].get(0), Min);
		}
	}
	
	private static void print() {
		for (int i = 0; i < N; i++) {
			System.out.print(arr[i].toString());
		}
		System.out.println();
	}
}

 

출처

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

23291번: 어항 정리