문제 링크: https://www.acmicpc.net/problem/23291
방법은 없다. 잘 구현하는 것 뿐
가장 큰 수와 가장 작은 수의 차이가 K 이하일 때까지 다음을 반복한다.
물고기 최소인 어항에 물고기 추가
어항 돌려 쌓기
물고기 수 조절
어항 일렬 배치
어항 접기 (2번 반복이기 때문에)
3의 물고기 수 조절 반복
어항 일렬로 배치
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;
}
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
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
=> 총 두 번 반복되며 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;
}
총평
문제에서 뭘 하라고 하는지 알겠는데 실제 코드로 구현하는 것은 쉽지 않았다.