[JAVA] 백준 26215번: 눈 치우기

< 문제 >

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

package silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P26215 {
	// 눈 치우기
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 집의 수
		int house[] = new int[n];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			house[i] = Integer.parseInt(st.nextToken());
		}

		int time = 0;
		int max_index = n - 1;
		
		if(n==1) {
			time= house[0];
		}
		else {
			while (true) {
				Arrays.sort(house); // 오름차순 정렬

				if (house[max_index] == 0 && house[max_index - 1] == 0)
					break;

				house[max_index]--;

				if (house[max_index - 1] != 0)
					house[max_index - 1]--;

				time++;

			}
		}

		if (time > 1440)
			System.out.println("-1");
		else
			System.out.println(time);
	}

}

 

✏️ 풀이 방법

 

⭐ 눈을 전부 치우는 데 걸리는 시간을 최소로 할려면 한 번에 두 집을 치우는 경우를 늘리고, 한 집을 치우는 경우를 줄여야한다. 그러므로 정렬을 계속 반복하여 가장 눈이 많이 쌓여있는 집을 먼저 치우는 방식으로 문제를 해결해야 한다 ! 

 

1. 변수 n에 집의 수를 입력받는다.

2. n의 크기만큼의 배열 house를 생성하여 눈의 양을 저장한다.

3. 배열의 크기가 1일 때 -> 입력 받은 눈의 양만큼의 시간이 걸림

    배열의 크기가 1이 아닐 때 -> 반복문 ( 가장 큰 두 개의 값이 0일 때까지 반복문 돌기=> 모든 집 앞의 눈을 다 치웠다는 뜻) 

    : 매 반복마다 배열을 오름차순으로 정렬한다.

    : 배열에서 가장 큰 값과 그 다음으로 큰 배열의 값을 감소시킨다. ( 한 번에 두 집 선택 가능하므로)

    : 걸리는 시간을 증가시킨다.

4. 걸리는 시간을 저장한 변수 time 을 출력한다. 

 

✍🏻 느낀점

 

이 문제를 풀면서, 문제를 풀기 전에 어떻게 풀어야하는지 생각을 하며 손으로 풀어보는 것이 굉장히 중요하다는 것을 또 깨달았다. 먼저 손으로 풀어보고 이렇게 코딩하면 되겠다! 생각하고 푸니까 빠른 시간에 문제를 해결할 수 있었다. 이것을 잊지 말자!