SWEA 14510. 나무 높이 (C++)

요약

필요한 2의 개수와 1의 개수를 cnt1, cnt2에 저장
1의 개수가 2의 개수보다 작을때까지 cnt2 한개를 cnt1 두개로 바꿔주는 작업을 했다.

---

문제

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




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

[입력]
각 테스트 케이스의 첫째 줄에는 나무의 개수 N이 주어진다.
다음 줄에는 나무들의 높이가 N개의 자연수로 주어진다.

[출력]
최소 날짜 수를 출력한다.

---

풀이

#include<iostream>
#include <vector>
using namespace std;

int N;
int cnt1, cnt2;
int max_height;
vector<int>tree;
vector<int>need_water;


// 가장 큰  나무의 키를 기록하고 그 차이들을 벡터에 넣자.

void init() {

	cin >> N;
	max_height = 0;

	for (int i = 0; i < N; i++) {

		int height;
		cin >> height;
		tree.push_back(height);
		if (height > max_height) max_height = height;
	}

	for (int i = 0; i < tree.size(); i++) {
		need_water.push_back(max_height - tree[i]);
	}
}

int calc() {

	cnt1 = 0;
	cnt2 = 0;

	for (int i = 0; i < tree.size(); i++) {

		cnt1 += need_water[i] % 2;
		cnt2 += need_water[i] / 2;
	}

	if (cnt1 == 0 && cnt2 == 0) return 0;
	else if (cnt1 != 0 && cnt2 == 0) {
		return cnt1 * 2 - 1;
	}

	else if (cnt1 == cnt2) return cnt1 * 2;
	else if (cnt1 > cnt2) return cnt1 * 2 - 1;
	else if (cnt2 > cnt1) {
		while (cnt1 < cnt2 - 1) {
			if (cnt2 - 2 == cnt1) {
				return (cnt1 + 2) * 2 - 1;
			}
			cnt1 += 2;
			cnt2--;
		}
		return cnt2 * 2;
	}
}


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();

	int T;
	cin >> T;

	for (int tc = 1; tc <= T; tc++) {
		tree.clear();
		need_water.clear();
		init();
		int ans = calc();
		cout << "#" << tc << " " << ans << "\n";
	}
	return 0;
}