23291: 어항 정리

wnajsldkf·2022년 10월 13일
0

Algorithm

목록 보기
7/58
post-thumbnail

문제 링크: https://www.acmicpc.net/problem/23291

설명

방법은 없다. 잘 구현하는 것 뿐

가장 큰 수와 가장 작은 수의 차이가 K 이하일 때까지 다음을 반복한다.

  1. 물고기 최소인 어항에 물고기 추가

    • 물고기가 최소인 어항을 찾고 물고기를 1씩 추가한다.
  2. 어항 돌려 쌓기

    • 처음에는 가장 왼쪽의 1개 항만 이동한다.
    • 쌓여있는 모든 어항을 시계 방향으로 90도 회전시켜 쌓는다.
  3. 물고기 수 조절

    • 상하좌우 인접 어항을 확인하며, 현재 어항과 인접한 어항의 물고기 수를 비교한다.
    • (현재 어항 - 이동할 어항)/5 > 0이면, 물고기를 이동한다.
  4. 어항 일렬 배치

    • 쌓인 어항을 일렬로 배치한다.
    • 가장 왼쪽에 있는 어항부터 양의 y 방향으로 하나씩 배치한다.
  5. 어항 접기 (2번 반복이기 때문에)

    • 가운데를 중심으로 왼쪽을 180도 회전시켜 오른쪽 위에 배치한다.
  6. 3의 물고기 수 조절 반복

  7. 어항 일렬로 배치

코드

addFish
물고기가 최소인 어항에 1 추가하기

private static void addFish() {
	int min = findSmallest();
    for(int i = 0; i < N; i++) {
    	if(bowl[0][i] == min) {
        	bowl[0][i]++;
		}
	} 
}    

private static int findSmallest() {
	int smallest = bowl[0][0];
    for (int i = 0; i < N; i++) {
    	if (smallest > bowl[0][i] {
        	smallest = bowl[0][i];
        }
	}
    return smallest;
}
  • 0번째 줄에서 가장 작은 값을 찾는다.
  • 반복문을 통해 0번째 줄을 돌면서 찾은 작은 값과 일치하는 값에 1을 더한다.

rotateBlocks
어항 돌려 쌓기

private static void rotateBlocks() {
	// width: 회전시킬 것의 가로 길이, height: 회전시킬 것의 세로 길이, 회전시킨 것을  쌓을 시작 인덱스
	int width = 1; height = 1; start = 1;
    int index = 0;
    
	// 배열의 index는 배열의 크기 - 1까지 존재하기 때문에 미리 1을 빼둔다.
    while (start + height - 1 < N) {
    	index += 1;		// 이 다음에 회전시킬 것이 가로로 증가하는지, 세로로 증기하는지 표시
        for (int y = 0; y < height; y++) {
        	for (int x = start - width; x < start; x++) {	// 가로 시작
            	bowl[start - x][start + y] = bowl[y][x];
                bowl[y][x] = 0;
			}
		}
        start += height;
        
        if (index % 2 == 0) width += 1;
        else height += 1;
	}
}    

adjustBlocks
물고기 수 조절하기

  • 조정한 결과를 담을 배열을 생성해둔다.
private static void adustBlocks() {
	int[][] temp = new int[N][N];
    
    for(int i = 0; i < N; i++) {
    	for(int j = 0; j < N; j++) {
        	// x,y 축에서 각각 한 방향씩만 확인해도 모든 원소를 이렇게 확인하기 때문에 상관없음
        	calcDiff(temp, i, j, i + 1, j);	// y 방향에서 확인
            calcDiff(temp, i, j, i, j + 1); // x 방향에서 확인
		}            
	}
    
    for(int i = 0; i < N; i++) {
    	for(int j = 0; j < N; j++) {
        	bowl[i][j] += temp[i][j];	// temp에 업데이트 해둔 것들을 원래 배열에 대입
		}
	}       
}

private static void calcDiff(int[][] temp, int y1, int x1, int y2, int x2) {
	// 비어있는 원소에서는 아무것도 하지 않는다.
    if (bowl[y1][x1] == 0) return;
    if (bowl[y2][x2] == 0) return;
    
    int value = Math.abs(bowl[y1][x1] - bowl[y2][x2]) / 5;
    if(bowl[y1][x1] > bowl[y2][x2]) {
    	temp[y1][x1] -= value;
        temp[y2][x2] += value;
	} else {
    	temp[y1][x1] += value;
        temp[y2][x2] -= value;
	}
}    

arrangeBlocks

  • Block을 다시 일열로 정리한다.
  • 일열로 정리할 배열을 만들어 반복문을 돌며 정리하고, 마지막에 대입해준다.
private static void arrangeBlocks() {
	int[] temp = new int[N];
    int idx = 0;
    for (int x = 0; x < N; x++) {
    	for (int y = 0; y < N; y++) {
        	if (bowl[y][x] != 0) {
            	temp[idx++] = bowl[y][x];
                bowl[y][x] = 0;
			}
		}
	}
    
    // 일열로 정리한 temp 배열을 대입
    for (int i = 0; i < N; i++) {
    	bowl[0][i] = temp[i];
	}
}

foldBlocks

  • N/2개를 공중 부양시켜 시계 방향으로 180도 회전시킨 다음, 오른쪽 N/2개 위에 쌓는다.
  • 한번 더 반복하여 N/2개를 공중 부양시켜 시계 방향으로 180도 회전시킨 다음, 오른쪽 N/2개의 위에 놓는다.

=> 총 두 번 반복되며 3층이 쌓일 것이다.

private static void foldBlocks() {
	for (int i = 0; i < N/4; i++) {
    	bowl[1][N - 1 - i] = bowl[0][i];
        bowl[0][i];
	}
    
    for (int i = 0; i < N/4; i++) {
    	bowl[2][N / 4 * 3 + i] = bowl[0][N / 4 + i];
        bowl[0][N / 4 + i] = 0;
	}
    
    for (int i = 0; i < N / 4; i++) {
    	bowl[3][N - 1 - i] = bowl[0][M / 2 + i];
        bowl[0][N / 2 + i] = 0;
	}        
}

전체 코드

public class Main {
	static int N, K;
    static int[][] bowl;
    
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLiner())'
        
        N = Integer.parseInt(st.nextToken());	// 어항의 수
        K = Integer.parseInt(st.nextToken());	// 물고기 수 차이
        
        bowl = new int[N+1][N+1];
        
        st = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < N; i++) {
        	bowl[0][i] = Integer.parseInt(st.nextToken());
		}
        
        int count = 0;
        
        while(!isSuccess()) {
        	blockProcess()
        	count += 1;
        );
        
        System.out.println(count);
	}
    
    private static boolean isSuccess() {
    	int subtraction = findBiggest() - findSmallest();
        return subtraction <= K;
	}
    
    private static void blockProcess(){
    	addFish();
        rotateBlocks();
        adjustBlocks();
        arrangeBlocks();
        foldBlocks();
        adjustBlocks();
        arrangeBlocks()'
	}

	private static void foldBlocks() {
        for (int i = 0; i < N / 4; i++) {
            bowl[1][N - 1 - i] = bowl[0][i];
            bowl[0][i] = 0;
        }

        for (int i = 0; i < N / 4; i++) {
            bowl[2][N / 4 * 3 + i] = bowl[0][N / 4 + i];
            bowl[0][N / 4 + i] = 0;
        }

        for (int i = 0; i < N / 4; i++) {
            bowl[3][N - 1 - i] = bowl[0][N / 2 + i];
            bowl[0][N / 2 + i] = 0;
        }
    }

    // Block을 다시 일열로 만든다.
    private static void arrangeBlocks() {
        int[] temp = new int[N];
        int idx = 0;
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (bowl[y][x] != 0) {
                    temp[idx++] = bowl[y][x];
                    bowl[y][x] = 0;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            bowl[0][i] = temp[i];
        }
    }

    private static void adjustBlocks() {
        int[][] temp = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                calcDiff(temp, i, j, i + 1, j); // 아래 확인
                calcDiff(temp, i, j, i, j + 1); // 오른쪽 확인
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                bowl[i][j] += temp[i][j];   // temp 배열에 있는 것을 대입
            }
        }

    }

    private static void calcDiff(int[][] temp, int y1, int x1, int y2, int x2) {
        // 비어있으면 아무것도 안한다.
        if (bowl[y1][x1] == 0) return;
        if (bowl[y2][x2] == 0) return;

        int value = Math.abs(bowl[y1][x1] - bowl[y2][x2]) / 5;
        if (bowl[y1][x1] > bowl[y2][x2]) {
            temp[y1][x1] -= value;
            temp[y2][x2] += value;
        } else {
            temp[y1][x1] += value;
            temp[y2][x2] -= value;
        }
    }

    // 2. 회전시킨다. https://jangcenter.tistory.com/94 -> 그림으로 그려본다.
    private static void rotateBlocks() {
        int width = 1, height = 1, start = 1;   // start: N줄의 처음 시작 위치(pivot)
        int index = 0;  // 가로로 늘릴지, 세로로 늘릴지

        while (start + height - 1 < N) {

            index += 1;
            for (int y = 0; y < height; y++) {
                for (int x = start - width; x < start; x++) {
                    bowl[start - x][start + y] = bowl[y][x];
                    bowl[y][x] = 0;
                }
            }
            start += height;

            if (index % 2 == 0) width += 1;
            else height += 1;
        }
    }

    // 물고리를 집어 넣는다.
    private static void addFish() {
        int min = findSmallest();
        for (int i = 0; i < N; i++) {
            if (bowl[0][i] == min) {
                bowl[0][i]++;
            }
        }
    }

    // 가장 작은 물고기 찾기
    private static int findSmallest() {
        int smallest = bowl[0][0];
        for (int i = 0; i < N; i++) {
            if (smallest > bowl[0][i]) {
                smallest = bowl[0][i];
            }
        }
        return smallest;
    }

    // 가장 큰 물고기 찾기
    private static int findBiggest() {
        int biggest = bowl[0][0];
        for (int i = 0; i < N; i++) {
            if (biggest < bowl[0][i]) {
                biggest = bowl[0][i];
            }
        }
        return biggest;
    }

총평
문제에서 뭘 하라고 하는지 알겠는데 실제 코드로 구현하는 것은 쉽지 않았다.

profile
https://mywnajsldkf.tistory.com -> 이사 중

0개의 댓글