14510. 나무 높이

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AYFofW8qpXYDFAR4&categoryId=AYFofW8qpXYDFAR4&categoryType=CODE&&&

SW Expert Academy

 

문제

N개의 나무가 있다. 초기의 각 나무의 키가 주어진다. 하루에 한 나무에 물을 줄 수 있다. 첫 날은 물을 준 나무의 키가 1 자라고, 둘째 날은 물을 준 나무의 키가 2 자라고, 셋째 날은 물을 준 나무의 키가 1 자라는 식으로, 홀수 번째 날은 키가 1 자라고 짝수 번째 날은 키가 2 자란다. 모든 나무의 키가 처음에 가장 키가 컸던 나무와 같아지도록 할 수 있는 최소 날짜 수를 계산하라. 어떤 날에는 물을 주는 것을 하지 않을 수도 있다.

예를 들어 나무가 2그루이고 각각의 높이가 4와 2라고 하자. 첫째 날에 물을 주게 되면, 나무의 높이를 모두 4로 만들기 위해서는 3일째까지 물을 주어야 한다. 둘째 날은 아무 일도 안 하게 된다. 하지만, 첫째 날을 쉬고 둘째 날에 물을 주면 2일 만에 나무의 높이가 모두 4가 된다.

케이스 수 30, N 제한 100, 나무 높이 최대 120

[제약 사항]

1. 나무의 개수 N은 2 이상 100 이하이다. (2 ≤ N ≤ 100)
2. 주어지는 나무의 초기 높이는 1 이상 120 이하이다.

입력

가장 첫 줄에는 테스트 케이스의 총 수가 주어진다. 그 다음 줄부터 각 테스트 케이스가 주어지며, 각 테스트 케이스는 2줄로 구성된다. 각 테스트 케이스의 첫째 줄에는 나무의 개수 N이 주어진다. 다음 줄에는 나무들의 높이가 N개의 자연수로 주어진다.

출력

출력의 각 줄은 ‘#x’로 시작하고, 공백을 한 칸 둔 다음 가능한 최소 날짜 수를 출력한다. 단, x는 테스트 케이스의 번호이다.

 

이 문제를 풀 때 처음에는 백트래킹을 생각하고 풀었는데, 이 문제는 백트래킹으로 풀 수 없었다.

뭐… 내가 못 푼 거지 백트래킹으로 푼 사람이 있을 수도..?

아무튼 저는 그리디를 사용해서 문제를 해결했습니다.

 

우선, 경우에 따른 계산 식을 세워보면

1. 1의 개수가 2의 개수 보다 많을 경우
2. 1의 개수가 2의 개수 보다 적을 경우
3. 1과 2의 개수가 같을 경우

이렇게 3가지로 볼 수 있다. 그럼 규칙을 찾아보면

입력이 다음과 같다고 하자 그럼 필요한 높이는 1 1 1 2 가 된다.

 

이제 1 1 1 2에 대한 입력 순서를 보면

 

위 그림과 같이 5번의 입력이 최소의 날짜이다.

그럼 1의 개수가 2보다 많을 경우엔 2*(1의 개수) - 1의 식을 만들 수 있다.

 

그럼 2가 많은 경우를 살펴보자

 

똑같이 최소 5번의 입력이 발생한다. 그러나 다음과 같은 경우를 보자

 

이 경우는 입력을 한 번 건너 뛰는 경우가 더 이득이다.

그럼 두 입력의 차이는 무엇일까?

바로 1과 2의 개수의 차이가 1 이라는 점이다.

두 수의 차이가 1이고 2의 수가 더 많을 경우 2*(2의 개수)의 식이 나온다.

 

그럼 두 수의 개수가 같은 경우를 살펴보자

 

간단하게 서로 번갈아가며 물을 주면 끝이다.

즉 (1의 개수) + (2의 개수)의 식이 성립한다.

 

정리하면

odd = 1의 개수, even = 2의 개수라고 한다면

if(odd > even) {
	// 1의 개수 > 2의 개수
	최소 입력 = 2 * odd - 1;

} else if(odd < even) {
	// 1의 개수 < 2의 개수
	// 단, 1의 개수와 2의 개수의 차가 1일 경우
	최소 입력 = 2 * even;

} else {
	최소 입력 = odd + even;
}

 

위 조건이 성립하는데 문제는 2번째 규칙이다.

1과 2의 개수의 차가 1이 아니고 2가 더 많다면 해당 규칙이 성립하지 않는다.

 

2만큼 자라기 위해 물을 건너 뛰기 보다는 1을 2번 입력 받는게 더 이득이란 걸 알 수 있다.

즉 2의 개수 1개를 1의 개수 2개로 변경 가능하다.

 

이런 방식으로 1의 개수와 2의 개수의 차이가 1 이하로 맞추면 정의한 식을 적용할 수 있다.

그래서 최대 높이의 나무까지 자라야 하는데 필요한 높이의 숫자를 2를 중심으로 먼저 구하고 두 개수를 맞춰주면 된다.

//나무가 자라야 할 높이에서 필요한 1, 2의 개 수 구하기
int even = 0, odd = 0;
for (int i = 0; i < N; i++) {
	int diff = max - trees[i];
	
	if(diff == 0) continue;
	
	//2의 개수 중심으로 구하기
	even += diff / 2;
	odd += diff % 2;
}

//2 -> 1로 변경
if(even > odd) {
	while(Math.abs(even - odd) > 1) {
		even--;
		odd += 2;
	}
}

 

코드

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

/**
 * SWEA 14150. 나무 높이
 * @category 그리디
 */
public class Solution {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int tc = 1; tc <= T; tc++)
		{
			int N = Integer.parseInt(br.readLine());
			
			st = new StringTokenizer(br.readLine());
			
			int max = 0; //가장 큰 나무의 높이
			int[] trees = new int[N];
			for (int i = 0; i < N; i++) {
				int t = Integer.parseInt(st.nextToken());
				trees[i] = t;
				
				max = Math.max(max, t);
			}
			
			//나무가 자라야 할 높이에서 필요한 1, 2의 개 수 구하기
			int even = 0, odd = 0;
			for (int i = 0; i < N; i++) {
				int diff = max - trees[i];
				
				if(diff == 0) continue;
				
				even += diff / 2;
				odd += diff % 2;
			}
			
			//2 -> 1로 변경
			if(even > odd) {
				while(Math.abs(even - odd) > 1) {
					even--;
					odd += 2;
				}
			}
			
			int result = 0;
			if(odd > even) { //1이 많을 경우
				result = odd * 2 - 1;
				
			} else if(even > odd) { //2가 많을 경우 
				result = even * 2;
				
			} else { //1과 2의 숫자가 같을 경우
				result = odd + even;
			}
			
			System.out.println("#" + tc + " " + result);
		}
	}
}