PASS 받은 정답코드는 맨 밑에 있습니다.
시간 : 50개 테스트케이스를 합쳐서 C/C++의 경우 1초 / Java의 경우 1초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내
[문제]
N개의 나무가 있다. 초기의 각 나무의 키가 주어진다. 하루에 한 나무에 물을 줄 수 있다. 첫 날은 물을 준 나무의 키가 1 자라고, 둘째 날은 물을 준 나무의 키가 2 자라고, 셋째 날은 물을 준 나무의 키가 1 자라는 식으로, 홀수 번째 날은 키가 1 자라고 짝수 번째 날은 키가 2 자란다. 모든 나무의 키가 처음에 가장 키가 컸던 나무와 같아지도록 할 수 있는 최소 날짜 수를 계산하라. 어떤 날에는 물을 주는 것을 하지 않을 수도 있다.
예를 들어 나무가 2그루이고 각각의 높이가 4와 2라고 하자. 첫째 날에 물을 주게 되면, 나무의 높이를 모두 4로 만들기 위해서는 3일째까지 물을 주어야 한다. 둘째 날은 아무 일도 안 하게 된다. 하지만, 첫째 날을 쉬고 둘째 날에 물을 주면 2일 만에 나무의 높이가 모두 4가 된다.
케이스 수 30, N 제한 100, 나무 높이 최대 120
[제약사항]
나무의 개수 N은 2 이상 100 이하이다. (2 ≤ N ≤ 100)
주어지는 나무의 초기 높이는 1 이상 120 이하이다.
제시된 상황을 정리를 해보자.
- N 개의 나무가 각자의 높이를 가진다.
- 처음 상태에서 가장 키 큰 나무의 키가 모든 나무들의 목표 키다.
- 하루 한 나무에만 물을 줄 수 있다. 물을 아예 안주고 넘어갈 수도 있다.
- 홀수날에 물주면 1cm 자라고, 짝수날에 물주면 2cm 자란다.
생각
처음에 가장 키가 컸던 나무 키를 maxH 라고 하자.
모든 나무는 maxH 보다 크거나 작아지는게 아니라, 정확하게 같은 키가 되는게 목표라는 점이 중요했다.
그렇다면, maxH 와 차이가 홀수만큼 나는 나무들은, 물을 받은 날에 홀수날이 적어도 하루는 포함되어야 한다.
왜냐하면 키를 홀수만큼 키우는 방법과 짝수만큼 키우는 방법은 다음처럼 서로 차이가 있기 때문이다.
1cm : 홀수날 하루만큼 물주기
2cm : 짝수날 하루만큼 물주기 or 홀수날 두 번에 걸쳐 물주기
홀수만큼 차이나는 나무들 물주기 과정은
코드로 다음과 같이 표현했다.
int oddDiffTrees = 0; // 1cm 를 한 번은 받아야 하는 나무 수
int totalDiff = 0;
for (int j = 0; j < n; j++) {
int curDiff = maxH - trees[j];
totalDiff += curDiff;
if (curDiff % 2 == 1) {
oddDiffTrees++;
trees[j]++; // 차이의 짝수화
}
}
totalDiff -= oddDiffTrees;
// maxH 와의 차이가 홀수인 나무들에 모두 1cm 를 줬을 때의 최소 days
int days = 2 * oddDiffTrees - 1;
// days 동안 사용할 수 있었던 2cm 들의 합
int usableH = days - 1;
홀수날에 줄 물을 계산한 와중에,
짝수날에 물을 줄 수 있는 기회들은 아직 사용하지 않았기 때문에 usableH 라는 변수에 저장해둔다.
maxH 와 각 나무들의 높이 차를 모두 합한 값은 totalDiff 에 저장했다.
만약 usableH 가 totalDiff 이상이라면 더 이상 물을 줄필요가 없으므로 정답이 도출되지만
아마 그렇게 간단한 테스트케이스만 있지는 않을 것이므로 totalDiff - usableH 만큼의 물을 더 줘야하는 상황을 생각해보자.
홀수일에 최소 한 번은 물을 받야아 하는 나무들에 물을 주며
maxH 와 각 나무들의 차이를 모두 짝수화 할 수 있다.
이제 문제는 홀수날에 2cm 를 키우고, 짝수날에 1cm 를 키울 수 있으며
모든 나무가 maxH 와의 키 차이가 짝수만큼 나게되는 새로운 문제로 바뀌었다.
이렇게 모든 차이를 짝수화 하게되면 좋은 점이있다.
아까 살펴봤듯이 2cm 를 키우는 방법은 2가지가 있기 때문에,
얼마만큼 차이가 나던 간에 최적의 물주기를 보장할 수 있다.
이게 무슨 말인지 이해하기 위하여, 차이의 짝수화를 실행하지 않은 예시를 하나 살펴보자.
<차이 짝수화가 이뤄지지 않은 경우>
나무들의 높이 : [10, 9, 9, 9, 9]
maxH = 10
totalDiff = 4
차이의 짝수화를 진행하지 않았다면, 위 테스트케이스를 해결하기 위해 필요한 날짜는
총 차이 4cm 를 키울 수 있는 3일이 아닌 7일이다. (1, 3, 5, 7 일에만 물을 1cm 줘야함.)
즉 어떤 날짜를 건너뛸지 말지에 대해 생각을 해야만 한다.
반면 차이의 짝수화가 이루어진 경우를 살펴보자.
<차이 짝수화가 이뤄진 경우>
나무들의 높이 : [10, 6, 8, 6, 8]
maxH = 10
totalDiff = 12
이렇게 차이의 짝수화를 진행했다면
위 테스트케이스를 해결하기 위해 필요한 날짜는 총 12cm 를 키울 수 있는 8일이 된다.
홀/짝수날에 물주기를 쉴 것 인가에 대한 고민이 필요없어 진다는 것이다.
다만 앞에서 언급했듯이, 차이의 짝수화를 진행하면서
days 변수에 필요한 필수 홀수날을 반영했으므로
남은 높이들의 처리는 짝수날부터 시작하는 문제라고 생각하면 된다.
그럼 이제 추가로 키워야 하는 높이 총합을 totalDiff - usableH 를 toGrowH 라고 하고,
toGrowH 만큼을 키우기 위해 필요한 날짜 수를 i 라고 한다면
totalDiff - usableH <= i + (i + 1)/2
위 점화식을 만족하는 최소의 i 를 찾았을 때 i + days 가 최종 정답이 된다.
점화식은 각 날짜에 키울 수 있는 최대 키 누적합 수열을 써보면 구할 수 있다.
i : 1 2 3 4 5 6 ...
h : 2 3 5 6 8 9 ...
정답 코드에는 while 문을 통해 i를 1씩 증가시키며 최소가 되는 i 를 찾았는데,
이는 toGrowH 가 굉장히 큰 수일 경우 시간복잡도 측면에서 문제가 될 수 있다.
때문에 위 점화식을 i 를 기준으로 정리하여
다음과 같이 최적화된 계산으로 i 를 얻을 수 있다.
int i = (int) Math.ceil((2.0 * toGrowH - 1.0) / 3.0);
아래는 전체 소스코드이다.
import java.io.*;
import java.util.StringTokenizer;
class Solution {
// 나무 높이 (SWEA)
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int tc = Integer.parseInt(br.readLine());
for (int i = 0; i < tc; i++) {
bw.write("#"+(i+1)+" ");
int n = Integer.parseInt(br.readLine());
int[] trees = new int[n];
int maxH = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int h = Integer.parseInt(st.nextToken());
maxH = Math.max(maxH, h);
trees[j] = h;
}
int oddDiffTrees = 0; // 1cm 를 한 번은 받아야 하는 나무 수
int totalDiff = 0;
for (int j = 0; j < n; j++) {
int curDiff = maxH - trees[j];
totalDiff += curDiff;
if (curDiff % 2 == 1) {
oddDiffTrees++;
trees[j]++; // 차이의 짝수화
}
}
totalDiff -= oddDiffTrees;
int days = 2 * oddDiffTrees - 1; // maxH 와의 차이가 홀수인 나무들에 모두 1cm 를 줬을 때의 최소 days
int usableH = days - 1; // days 동안 사용할 수 있었던 2cm 들의 합
if(usableH >= totalDiff) {
bw.write(days + "\n");
continue;
}
int toGrowH = totalDiff - usableH; // 더 키워야 하는 총 높이
// days 는 이제 짝수일, i 는 1부터 시작하는 자연수.
// toGrowH <= i + (i+1)/2 를 만족하는 가장작은 i 찾아 days 에 추가
int extraDays = 1; // i
while(toGrowH > extraDays + (extraDays+1)/2) {
extraDays++;
}
days += extraDays;
bw.write(days + "\n");
}
bw.flush();
}
}