[SWEA:14510/JAVA] 나무 높이

 

 

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AYFofW8qpXYDFAR4

SW Expert Academy

 

 

1. 문제 요약

첫 날은 물을 준 나무의 키가 1 자라고, 둘째날은 물을 준 나무의 키가 2 자라고, 셋째날은 물을 준 나무의 키가 1 자라는 식. 

홀수 번째 날은 키가 1자라고, 짝수번째 날은 키가 2 자란다. 

모든 나무의 키가 가장 키가 컸던 나무의 키와 같아지도록 할 수 있는 최소 날짜 수 구하기

 

※ 주의할 점

최소 날짜 수를 구하기 위해 물을 안주는 날도 가능하다. 

 

---

 

2. 알고리즘 [접근 방법] 

1. 먼저 입력값에서 가장 키가 큰 나무의 키를 저장하는 max 변수가 필요하다. 
2. [max - 현재 나무의 키] 를 하여 모든 나무의 키가 max 변수만큼 자라려면 얼마만큼의 성장량이 필요한지 계산한다. 
3. growth 가 0일 경우에는 해당 나무가 키가 가장 큰 나무이기 때문에 반복문을 돌 때 제외한다. 
4. 성장량의 최소 홀수 day 와 최소 짝수 day 를 각각 totalOddDay, totalEvenDay 에 누적시킨다. 

 [4, 2, 1] 순서로 나무의 키를 담은 배열이 있다고 가정하자

그럼 max 값은 4 이고 각각의 나무 성장량은 0, 2, 3 이다. 

0을 제외한 2와 3이 성장을 하려면 각각의 (홀,짝) 이 (0, 1), (1, 1) 이 된다. 

즉, 성장량 2를 가진 나무는 홀수 day 는 0일, 짝수 day 는 1일을 가지게 되어
1일차(물X), 2일차(물O) => 키2 + 물2cm = 4cm 가 된다. 

또한, 성장량 3을 가진 나무는 홀수 day 는 1일, 짝수 day 는 1일을 가지게 되어 

1일차(물O), 2일차(물O) => 키1 + 물1cm + 물2cm = 4cm 가 된다. 

이를 totalOddDay 에 누적하게 되면 성장량 2의 홀수 0, 성장량 3의 홀수 1 을 하여 총 totalOddDay 는 1이 되고, 

totalEvenDay 에는 성장량 2의 짝수1, 성장량 3의 짝수 1을 하여 총 totalEvenDay 는 2가 된다. 

5. 짝수day 가 더 클수록 최소날짜수는 최소가 아니게 되기 때문에, 홀수와 짝수의 균형을 맞춰주기 위해 균형을 맞춰주는 작업을 한다. 

 

6. 총합을 구하는 작업을 홀수누적합이 더 큰 경우, 짝수 누적합이 더 큰 경우, 그리고 같은 경우를 나눠 아래와 같이 진행한다. 

<홀수누적합이 더 클 경우>

예를 들어,  totalOddDay 이 3일, totalEvenDay 2일 일 때

홀수 day 를 일자까지 표현하려면, totalOddDay * 2 - 1 를 해야함.
(즉 3일인 경우, 1,3,5일을 거쳐 총 5일까지 가야하므로 3*2-1)

 

<짝수 누적합이 더 큰 경우>

예를 들어,  totalOddDay 이 2일, totalEvenDay 4일 일 때

짝수 day 를 일자까지 표현하려면, totalEvenDay * 2 를 해야함.

(즉 4일인 경우, 2,4,6,8일을 거쳐 총 8일까지 가야하므로 4*2)

 

<짝수 누적합 + 홀수 누적합> 인 경우 

예를 들어, totalOddDay 이 5일, totalEvenDay 5일 일 때, 

totalOddDay + totalEvenDay 를 하면 된다. 

(1,2,3,4,5,6,7,8,9,10일을 거쳐 총 10일까지 가야하므로 5+5)

 

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

public class SWEA_14510_나무높이 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			int N = Integer.parseInt(br.readLine());
			int[] trees = new int[N];
			
			// 나무 담기
			int max = Integer.MIN_VALUE;
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int n = 0; n < N; n++) {
				trees[n] = Integer.parseInt(st.nextToken());
				// 키가 가장 큰 나무 max 에 담기 
				max = Math.max(max, trees[n]); 
			}
			
			int totalOddDay = 0; // 최소홀수값
			int totalEvenDay = 0; // 최소짝수값
			for(int i = 0; i < N; i++) {
				
				// 성장량 기록 
				int growth = max - trees[i];
				if(growth != 0) { // growth 가 0인 경우, 가장 키가 큰 나무이기때문에 제외
					totalOddDay += growth % 2; // 홀수
					totalEvenDay += growth / 2; // 짝수
				}
			}
			
			// 균형을 맞춰주기 위해 작업 
			if(totalEvenDay > totalOddDay) {
				while(Math.abs(totalEvenDay - totalOddDay) > 1) {
					totalEvenDay--; 
					totalOddDay += 2; 
				}
			}
			
			int totalDay = 0;
			if(totalOddDay > totalEvenDay) {
				totalDay = 2 * totalOddDay - 1; 
			} else if(totalEvenDay > totalOddDay) {
				totalDay = 2 * totalEvenDay; 
			} else {
				totalDay = totalOddDay + totalEvenDay;
			}
			
			System.out.println("#" + t + " " + totalDay);
		}
				
	} // main
}