https://www.acmicpc.net/problem/19539
▲ 문제 바로가기

물뿌리개를 한 번 사용할 때마다

• 서로 다른 두 나무에 각각 1, 2만큼 사용
• 한 나무에 1+2만큼 사용

시킬 수 있다. 결국 1과 2를 동시에 사용하는 조합만으로 입력의 형태를 만들 수 있는지를 물어보는 문제이다.

풀이

early return

먼저 물뿌리개를 한 번 사용할 때마다 전체 나무는 3만큼 성장한다는 것을 알 수 있다. 따라서 입력의 합이 3의 배수가 아니면 NO를 출력하고 종료해야 한다.

처음에는 쉽게 생각나지 않아서 몇 가지 예시를 들어 동작의 특징들을 살펴보았다.

example 1

1 1 1 3 3

편의상 1, 2씩 빼면서 모든 수를 0으로 만들어보겠다.

1 1 1 3 3 -> 0 1 1 1 3 -> 0 0 1 1 1 -> NO

1을 없애려면 2가 반드시 필요하다. 하지만 3의 경우 두 물뿌리개를 동시에 사용하면 본인만 사라지고, 2짜리 물뿌리개를 사용하면 다시 1이 남게 된다.

따라서 1과 짝이 되어 없어질 수 있는 2의 개수를 세어야겠다고 생각했다.

위의 예시 1 1 1 3 3의 경우, 2의 개수는 두 개다. 각 숫자를 2로 나눈 몫의 합이다. 반면 1의 개수는 다섯 개다. 1이 세 개 있고, 3을 2로 나눈 나머지가 1이기 때문에 두 개가 더해진다.

정리해 보면,

• 1이 5개
• 2가 2개

두 개씩은 짝을 맞추어 없어지지만, 1이 세 개 남기 때문에 이 경우 NO가 되는 것이다.

example 2

1 1 4의 경우는 어떨까?

1 1 4 -> 0 1 2 -> 0 0 0 -> YES

1과 2의 개수를 세어 보면,

• 1이 2개
• 2가 2개

짝이 맞춰져 모두 없어지게 된다. 남는 것이 없기 때문에 YES가 된다.

example 3

1 4 4의 경우는 어떨까?

1 4 4 -> 0 2 4 -> 0 1 2 -> 0 0 0 -> YES

1과 2의 개수를 세어 보면,

• 1이 1개
• 2가 4개

하나의 짝이 만들어져 없어지고, 2가 세 개 남게 된다. 그런데 어떻게 YES가 될까?

남은 세 개의 2 중에 하나를 1 두 개로 생각할 수 있다. 그렇게 되면 다시 1이 두 개, 2가 두 개가 되어 짝이 맞추어 사라지게 된다. 실제로 위 과정에서 보면 (1, 2)씩 세 번 물뿌리개를 사용한다.

한 가지 의심

여기서 의심이 들었다. example 3의 경우 2가 세 개 남았기 때문에 그 중 하나를 1로 변환해서 짝을 맞추었다.

하지만 2가 한 개 또는 두 개 남으면?

사실 이 부분은 간단하다. 짝을 맞추어 없어진 것들은 모두 3의 배수이다. 여기에 2가 한 개 또는 두 개 남게 되면 입력값의 합이 $3k+1$ 또는 $3k+2$ ($k$는 음이 아닌 정수)라는 뜻이 된다. 따라서 이런 경우는 early return에서 걸러지게 된다.

결론

위의 예시 이외에도 여러 예시를 들어보면서 내린 결론은 다음과 같다.

• 1을 없애기 위해 충분한 2가 있어야 한다.

1. 입력의 각 숫자들을 2로 나눈 몫의 합을 2의 개수로 둔다.
2. 입력의 각 숫자들을 2로 나눈 나머지가 있는 경우 1의 개수로 둔다.
3. 2의 개수가 1의 개수보다 크거나 같으면 YES, 아니면 NO를 출력한다.

---

다른 풀이의 비교식

정답을 받고 나서 다른 풀이들을 살펴보았다. 많은 풀이들이 2의 개수를 구하는 것까지는 동일하지만, 그 비교 대상이 1의 개수가 아니라 (입력값의 합)/3으로 달랐다. 입력값의 합을 3으로 나눈다는 것은 물뿌리개를 사용하는 전체 횟수가 된다. 2짜리 물뿌리개를 전체 사용 횟수 이상으로 사용할 수 있다는 조건도 직관적이라 생각한다.

얼핏 보면 내 논리와 달라 보이는데, 두 비교 모두 정답 처리를 받았다. 그래서 두 비교가 같은 비교인지를 수식으로 보이고 싶었다.

수식으로 증명하기

• 2의 개수 $t$
• 1의 개수 $o$
• 입력값의 합 $sum$
• 물뿌리개를 사용하는 전체 횟수 $D$ ($sum/3=D$)

라고 하자.

1, 2의 개수와 입력값의 합의 관계를 식으로 쓰면
$sum = 2t+o$

$D$를 $t$, $o$에 관한 식으로 쓰면
$3D=2t+o$, $D=\frac{2t+o}{3}$

내 풀이의 비교식 -> 다른 풀이의 비교식
$t\ge o \Leftrightarrow 3t\ge 2t+o$
$\space\space\space\space\space\space\space\space\space\space\Leftrightarrow t\ge \frac{2t+o}{3}=D$

따라서, $t\ge o$와 $t\ge D$은 같은 비교식이다.

식을 적절히 변형해서 같은 식임을 증명할 수 있었다.

마무리

1의 개수와 물뿌리개의 전체 사용 횟수는 얼핏 보면 다르게 보였지만, 수식으로 두 비교식이 같은 것임을 보였다. 많은 사람들이 작성한 풀이의 로직도 함께 알아두어야겠다.

틀린 부분이 있다면 언제든 피드백 남겨주세요 :)