백준 9037번 <The Candy War>

백준 알고리즘 9037번

https://www.acmicpc.net/problem/9037

9037번: The candy war

---

9037번

입력으로 첫 줄에 테스트케이스의 수 N이 들어온다. 그 다음 줄 부터 N개의 테스트케이스에 대한 정보가 들어온다.

테스트케이스는 아이들의 수가 주어지고 그 다음 줄에 각 아이들이 가진 사탕의 수가 주어진다.

 

출력으로는 몇 번의 놀이 과정을 거쳐야 각 테스트케이스에서 아이들이 같은 수의 사탕을 갖게 되는지 출력하면 된다.

 

놀이 과정

- 모든 아이들은 동시에 자기가 가지고 있는 사탕의 절반을 오른쪽 아이에게 준다.

- 홀수 개의 사탕을 가지고 있으면 선생님이 짝수로 보충해준다.

- 위의 2개의 과정이 1순환수에 속한다.

- 처음에 홀수 개의 사탕을 가지고 있을 경우에 선생님이 짝수로 보충해주는 것은 순환수에 들어가지 않는다.

---

문제 해결

count는 순환수를 의미한다.

0. 홀수 개의 사탕을 갖고 있는 아이들에게 선생님이 사탕을 1개씩 준다.

1. 모든 아이들이 같은 수의 사탕을 가지고 있는지 확인한다.

2-1. 가지고 있다면 count를 반환한다.

2-2. 가지고 있지 않다면 모든 아이들이 동시에 자기가 가지고 있는 사탕의 절반을 오른쪽 아이에게 준다.

3. 홀수 개의 사탕을 갖고 있는 아이들에게 선생님이 사탕을 1개씩 준다.

모두 같은 수의 사탕을 갖을 때까지 1부터 3까지를 반복한다.

 

0, 3번을 수행하는 teacher 함수를 구현하고 모든 아이들이 같은 수의 사탕을 가지고 있으면 true를 반환하여 while문을 멈추도록 하는 check 함수를 구현하였다.

teacher 함수와 check 함수를 활용하여 위의 과정을 구현하였다.

---

코드

def answer(n, candies):
    candies = teacher(n, candies)
    count = 0
    while True:
        if check(n, candies):
            break
        new_candies = [0 for _ in range(n)]
        half_candies = [candies[i]//2 for i in range(n)]
        for i in range(n):
            if i == 0:
                new_candies[i] = candies[i] - half_candies[i] + half_candies[n-1]
            else:
                new_candies[i] = candies[i] - half_candies[i] + half_candies[i-1]
        candies = teacher(n, new_candies)
        count += 1
    return count

def check(n, candies):
    candy_sum = sum(candies)
    candy_avg = candy_sum // n
    for c in candies:
        if c != candy_avg:
            return False
    return True
        
def teacher(n, candies):
    for i in range(n):
        if candies[i] % 2 != 0:
            candies[i] += 1
    return candies
testcase = int(input())

for _ in range(testcase):
    n = int(input())
    candies = list(map(int, input().split()))
    print(answer(n, candies))

---

결과

---