알고리즘
[Java] 백준 19539번 사과나무
J3SUNG
2023. 8. 4. 02:46
728x90
그리디 문제입니다.
물뿌리개 2개가 주어집니다.
1. 1의 높이를 올리는 물뿌리개
2. 2의 높이를 올리는 물뿌리개
2개의 물뿌리개를 이용해서 나무의 높이를 주어진 높이로 정확히 맞출 수 있는지 구해야 합니다.
먼저 3으로 나누어 떨어지는지 확인했습니다.
3으로 나누어 떨어지지 않는 경우는 불가능한 경우입니다.
한번에 1과 2를 사용하며, 2의 경우 1을 2개 사용해서 만들 수 있습니다.
1의 경우 2를 이용해서 만들 수 없습니다.
중요한건 1의 개수가 2의 개수보다 많은지 찾으면 됩니다.
최대한 2를 많이 쓰는 방향으로 생각해봅니다.
11 => 2 2 2 2 2 1
10 => 2 2 2 2 2
7 => 2 2 2 1
3 => 2 1
1 => 1
위를 보았을 때 규칙은 1의 개수는 2로 나누어 떨어지지 않는 수는 1을 하나 가집니다.
모든 수에 위처럼 2와 1의 개수를 나누어서 카운트해줍니다.
1이 2보다 많은 경우 실패한 경우로 출력해주었습니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int sum = 0;
int one = 0;
int two = 0;
String result = "YES";
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; ++i) {
int num = Integer.parseInt(st.nextToken());
sum += num;
one += num % 2;
two += num / 2;
}
if (sum % 3 > 0 || one > two) {
result = "NO";
}
bw.write(result + "\n");
bw.close();
}
}