19539

날짜 : 2022. 12. 11

사용 언어 : python

 

문제

 

 

코드

틀린코드

import sys

n = int(sys.stdin.readline())  # 사과나무 개수
t = list(map(int, sys.stdin.readline().split()))
t.sort(reverse=True)

for i in range(n-1):
    print(t)
    if t.count(2) == t.count(1):
        print("YES")
        exit()
    t[i] = t[i] % 3
    if t[i] == 1:
        if t[i+1] - 2 >= 0:
            t[i+1] = t[i+1] - 2
            t[i] = 0
        else: continue
    elif t[i] == 2:
        if t[i + 1] - 1 >= 0:
            t[i+1] = t[i+1] - 1
            t[i] = 0
        else: continue
    else:
        continue

print(t)
if t[-1] % 3 == 0: print("YES")
else: print("NO")

 

정답

import sys

n = int(sys.stdin.readline())  # 사과나무 개수
t = list(map(int, sys.stdin.readline().split()))

a, b = divmod(sum(t), 3)  # 3으로 나눈 몫과 나머지

if b != 0:
    print("NO")  # 총합이 3의배수가 아닌 경우
else:
    one, two = 0, 0
    for i in t:
        two += (i // 2)
        if i % 2 == 1: one += 1
    while True:
        if one == two:
            print("YES")
            break
        elif two > one:
            two -= 1
            one += 2
        elif one > two:
            print("NO")
            break

 

풀이

- 먼저 총합이 3의 배수가 아닌 경우 무조건 원하는 높이를 만들 수 없기 때문에 "NO"를 출력

- 그 다음 모든 수를 2, 1로 표현할 수 있기 때문에 각 수를 2로 나눈 몫(two)과 나머지가 1인 개수(one)을 구하여 쌍을 만든다.

예를들어 3 3 3 3 2 2 1 1 의 경우

3 = 2 * 1 + 1 * 1

2 = 2 * 1 + 1

1 = 1

이므로, (6, 6)이 도출된다.

이 경우 2가 6번, 1이 6번 나타나기 때문에 동일한 횟수로 물을 주었다는 것을 알 수 있기 때문에 YES를 출력할 수 있다.

 

그렇다면 1 1 1 3 3 은 어떨까?

3 = 2 * 1

1 = 1

이기 때문에 해당 수열에서 순서쌍은 (2, 5)가 나온다. 이 경우 1을 묶는 경우는 발생할 수 없기 때문에 해당 조건을 저절로 "NO" 가 도출된다. (수열에서 1과 1을 합치는 것은 불가능하기 때문이다.)

 

다른 예시를 들어본다면, 7 6 3 2를 들 수 있다.

7 = 2 * 3 + 1

6 = 2 * 3

3 = 2 * 1 + 1

2 = 2 * 1

(8, 2) 이 도출되고, 2를 쪼개면서 진행한다면, (7. 4) -> (6. 6) 처럼 동일한 지점이 나타난다.

그렇기에 해당 수열은 "YES"를 출력한다.

 

 

알게된 점

- 내림차순으로 정렬한 다음 하나하나 줄여가면서 값을 진행시키려 했지만 약 15%에 도달하면서 반례에 걸리게 되었다.

반례) 3 3 3 3 2 2 1 1

- 그래서 다른 풀이를 찾아보았고 아래 참고사이트를 보고 나에게 맞는 풀이를 찾아냈다.

 

 

참고 사이트

- https://velog.io/@axiom0510/b19539

백준 사과나무(19539)