[백준/JAVA] 23291 어항 정리

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

23291번: 어항 정리

문제 정리

1. 가장 물고기가 작게 들어있는 어항에 물고기 한마리를 넣는다. (최소값이 여러개면 모든 최솟값인 어항에 한마리씩 넣는다)

2.

다음과 같은 순서로 어항을 쌓는다 

     * 1. 초기: 제일 왼쪽 어항을 그다음 어항위에 올린다.

     * 2. 이후: 높이가 2이상인 모든 열을 시계방향으로 회전시킨 후 높이가 1인 열 위에 쌓는다

     * 3.밑의 그림과 같이 어항이 공중에 뜨기 전까지 반복한다. 

3. 이후 모든 인접한 두 어항에 대해서, 물고기 수의 차이를 구한다. 이 차이를 5로 나눈 몫을 d라고 하자. d가 0보다 크면, 두 어항 중 물고기의 수가 많은 곳에 있는 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다. 이 과정은 모든 인접한 칸에 대해서 동시에 발생한다

4. 가장 왼쪽에 있는 어항부터, 그리고 아래에 있는 어항부터 가장 위에 있는 어항까지 순서대로 바닥에 놓는다.

5. 이후 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전 시킨 다음, 오른쪽 N/2개의 위에 놓아야 한다. 이 작업은 두 번 반복해야한다. 두 번 반복하면 바닥에 있는 어항의 수는 N/4개가 된다. 

6. 다시 어항속 3번에 했던 작업을 반복해준 후 4번과정으로 일렬로 바닥에 놓는다.

7. 어항에 있는 물고기의 최대 마리수와 최소마리수의 차가 k이하가 될때까지 반복하고 그 반복 횟수를 구하면 되는 문제이다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n,k;
	static int[][] arr;
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};

	static void init() throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		arr = new int[101][101];
        	arr[0] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
	}

	static void fill1(){
		List<Integer> idxs = new ArrayList<>();
		int min = Integer.MAX_VALUE;
		for(int i=0; i<n; ++i){
			if(arr[0][i]==min){
				idxs.add(i);
			}else if(arr[0][i]<min){
				idxs.clear();
				idxs.add(i);
				min = arr[0][i];
			}
		}
		for(int idx: idxs) arr[0][idx]++;
	}

	static void move1(){
		boolean flag = false;
		int r = 1;
		int c = 1;
		while(true){
			int[][] temparr = new int[c][r];
			for(int i=0; i<r; ++i){
				for(int j=0; j<c; ++j){
					temparr[j][r-i-1] = arr[i][j];
				}
			}
			for(int i=0; i<c; ++i){
				for(int j=0; j<r; ++j){
					arr[i][j] = temparr[i][j];
				}
			}
			for(int j = c; j<n; ++j){
				arr[c][j-c] = arr[r-1][j];
			}
			for(int i = r; i<101; ++i){
				for(int j=0; j<c; ++j){
					arr[j][i] = 0;
				}
			}

			if(!flag) r++;
			else c++;
			flag = !flag;
			if(r>n-(r*c)){
				break;
			}
		}
	}

	static void makeup(){
		int[][] temparr = new int[n][n];
		for(int x=0; x<n; ++x){
			for(int y=0; y<n; ++y){
				if(arr[x][y]==0) continue;
				for(int k=0; k<4; ++k){
					int nx = x+dx[k];
					int ny = y+dy[k];
					if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
					if(arr[nx][ny]>=arr[x][y]) continue;
					if(arr[nx][ny]==0) continue;
					int d = (arr[x][y]-arr[nx][ny])/5;
					if(d>0){
						temparr[nx][ny] += d;
						temparr[x][y] -= d;
					}
				}
			}
		}

		for(int i=0; i<n; ++i){
			for(int j=0; j<n; ++j){
				arr[i][j] += temparr[i][j];
			}
		}
	}

	static void makeOneLine(){
		int[] temparr = new int[101];
		int idx = 0;
		for(int j=0; j<n; ++j){
			for(int i=n; i>=0; --i){
				if(arr[i][j]==0) continue;
				temparr[idx++] = arr[i][j];
				arr[i][j] = 0;
			}
		}
		arr[0] = temparr.clone();
	}

	static void move2(){
		int r = 1;
		int c = n/2;
		for(int count=0; count<2; ++count){
			int[][] temparr = new int[r][c];
			for(int i=0; i<r; ++i){
				for(int j=0; j<c; ++j){
					temparr[r-i-1][c-j-1] = arr[i][j];
				}
			}
			for(int i=0; i<r; ++i){
				for(int j=0; j<c; ++j){
					arr[i+r][j] = arr[i][j+c];
					arr[i][j+c] = 0;
				}
			}
			for(int i=0; i<r; ++i){
				for(int j=0; j<c; ++j){
					arr[i][j] = temparr[i][j];
				}
			}
			r++;
			c /= 2;

		}
	}

	static int max_min(){
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		for(int y=0; y<n; ++y){
			int cur = arr[0][y];
			max = Math.max(cur,max);
			min = Math.min(cur,min);
		}
		return max-min;
	}

	public static void main(String[] args) throws IOException {
		int answer = 0;
		init();
		while(max_min()>k){
			answer++;
			fill1();
			move1();
			makeup();
			makeOneLine();
			move2();
			makeup();
			makeOneLine();
		}
		System.out.println(answer);
	}
}

 

 

문제 풀이

문제에서 시키는대로 구현만 하면 특별하게 주의 해야될 부분이 없는 문제이다.

메모리와 시간제한이 넉넉하기 때문에 편하게 풀이하면 된다.

1. 초기값 구성

arr = new int[101][101];
arr[0] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

arr를 어항을 다루는 배열로 사용하였고, n의 제한이 100이므로 100*100배열을 선언해 주었다.

그리고 (0,0)위치부터 처음 어항의 배열을 넣어주었다.

 

2. 가장 작은 어항에 물고기를 추가하기

최솟값들의 인덱스를 모두 구한뒤 해당 인덱스의 어항에 물고기를 한마리씩 추가시킴

 

3. 어항 이동시키기

공중부양 시켜야될 어항을 생각해보면 

(행,열) 으로 표기할때 

(1,1) (1,2) (2,2) (2,3) (3,3)...이렇게 행1,열1 개의 어항부터 시작해서 

열+1, 행+1 순서로 옮겨야 될 어항의 수가 증가한다. 따라서 순서에 맞춰 행과 열값을 증가시켜가며 들어서 회전시켜야될 범위를 구한다.

그리고 항상 열의값이 행의값보다 1크거나 같기때문에 0,0을 기준으로 회전을 하더라도 기존 어항에 간섭이 없음.

예를 들어 다음 그림에서 

(0,0) (0,1)
(1,0) (1,1)
(2,0) (2,1) (2,2) (2,3)
이렇게 블럭이 쌓여있고 회전해서 쌓아야될 블럭은 (0,0) (0,1) (1,0) (1,1) (2,0) (2,1) 블럭이고 이 블럭을 (0,0)을 기준으로 90도 회전시킨다고 해도 

다음과 같은 모양이 된다. 이후 11과 8을 땡겨주면 쌓기가 완성된다.

옮겨야될 어항의 높이값이 90도 회전하며 길이가 되므로 

회전하고 남은 어항의 개수보다 회전해야할 어항의 높이가 작아야 이동을 시킬 수 있다.

 

4. 이후 각 칸에 대해 차를 구하고 5를나눠 몫을 배분하는 과정을 거친다.

5. 행 r-1, 열 0부터 loop를 돌며 일렬로 만든다

6. 다시 3번에 했던 과정을 반복한다. 하지만 3번의 과정에서는 행+1, 열+1 을 하며 회전하고 쌓아나갔지만 이번엔 행을 반으로 나눠가며 쌓아가면 된다.

7. 6번의 과정을 두번 반복한 후 4,5번의 과정을 차례로 실행한다. 

8. 각 어항의 최소값과 최대값이 k이하인지 확인하고 아니라면 1번과정 부터 다시 실행한다.