[SWEA / Java] 14510번: 나무 높이 (D2)

문제 풀이 날짜: 2023.10.11
포스트 작성일: 2023.10.16

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

SWEA 14510번: 나무 높이 (D2)

 

키워드

그리디, 수학, 나머지 연산(모듈러)

 

풀이 접근법

• 모든 나무가 성장해야 하는 높이 (remains[i]) 를 2로 나눈 몫은 필요한 짝수 날짜의 수이고, 2로 나눈 나머지는 필요한 홀수 날짜의 수이다.
• 이때 홀수 날짜와 짝수 날짜의 수는 항상 쌍을 이루어야 한다. (예: 홀수 날짜에 3회 물을 주었다면 짝수 날짜에도 3회 물을 주어야 한다.
• 쌍을 이루지 않는 날짜는 하루를 쉬고 건너서 물을 준 것이다. (편의상 건너뛴 날을 ∅로 표현한다.)
  • 그런데, 짝수 날짜(∅ + 2m)는 '연달아서 물을 준 홀수 날짜와 짝수 날짜' 쌍(1m + 2m)으로 압축이 가능하다.
  • 예를 들어, 총 6m를 성장시킨 경우는  ∅ + 2m +  ∅ + 2m +  ∅ + 2m 로 나타낼 수도 있지만 1m + 2m + 1m + 2m 으로 나타낼 수도 있다. 이 경우 6일치의 성장을 4일치로 줄일 수 있다.
  • 우리는 최소 기간을 구해야 하므로 날짜를 압축해주어야 한다. 압축하고도 남은 나머지 날짜가 홀수라면 그냥 1일을 더해주고, 짝수라면 하루 쉰 것까지 포함해서 2일을 결과값에 더해준다.

 

코드

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

public class Solution {

	private static int[] trees;
	private static int[] remains;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {
			int N = Integer.parseInt(br.readLine());
			
			trees = new int[N];
			remains = new int[N];
			
			int maxHeight = 0;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int i = 0; i < N; i++) {
				trees[i] = Integer.parseInt(st.nextToken());
				maxHeight = Math.max(trees[i], maxHeight);
			}
			
			int oddCount = 0; //홀수 날짜의 갯수
			int evenCount = 0; //짝수 날짜의 갯수
			for(int i = 0; i < N; i++) {
				remains[i] = maxHeight - trees[i];
				
				oddCount += remains[i] % 2;
				evenCount += remains[i] / 2;
			}
			
			int result = oddCount + evenCount;
			if(oddCount < evenCount) { //짝수 일자는 홀수 일자로 압축할 수 있다 => 날짜 수를 더욱 줄여보자.
				int gap = (evenCount - oddCount) * 2; //쉬는 날을 포함한 짝수 날짜의 수 (∅ + 2)
				int remain = (gap / 3) * 2; //짝수 날짜를 홀수 날짜로 압축한다.
				
				if(gap % 3 == 2) { //압축하고 남은 나머지가 짝수 날짜라면
					remain += 2; //홀수 날짜도 함께 쉰다. (∅ + 2)
				} else if (gap % 3 == 1) remain += 1; //그렇지 않으면 홀수 날짜만 더한다.
				
				result = (oddCount * 2) + remain;
			} else if (oddCount - evenCount > 1){ //홀수가 더 많을 경우 : 1 ∅ 1 ∅ 1 ... => ∅의 개수를 더한다.
				result += (oddCount - evenCount - 1);
			}
			
			sb.append("#").append(test_case).append(" ").append(result).append("\n");
		}
		
		System.out.print(sb);
	}

}

---

처음에는 다른 방식으로 풀었다가 답이 제대로 나오지 않았다. 짝수 날짜의 개수와 홀수 날짜의 개수를 세야한다는 발상을 하지 못해, 해당 부분만 다른 사람의 풀이를 참고하여 풀었다. 

홀&짝에 따라 물을 주는 규칙을 찾고, 쉰 날짜를 더해주는 것이 특히나 중요한 부분이었다.

 

참고한 링크

https://velog.io/@woonchoi/SWEA14510-나무-높이