[파이썬] 백준 9037번 The candy war : list comprehension 연습

The candy war

문제

알고리즘 유치원 선생님인 영희는 간식시간이 되자 아이들에게 사탕을 나누어 주려고 하였다. 하지만 욕심 많고 제멋대로인 유치원 아이들은 차례대로 받으라는 선생님의 말을 무시한 채 마구잡이로 사탕을 집어 갔고 많은 사탕을 집어 간 아이가 있는가 하면 사탕을 거의 차지하지 못하고 우는 아이도 있었다.

말로 타일러도 아이들이 말을 듣지 않자 영희는 한 가지 놀이를 제안했다. 일단 모든 아이들이 원으로 둘러앉는다. 그리고 모든 아이들은 동시에 자기가 가지고 있는 사탕의 절반을 오른쪽 아이에게 준다. 만약 이 결과 홀수개의 사탕을 가지게 된 아이가 있을 경우 선생님이 한 개를 보충해 짝수로 만들어 주기로 했다. 흥미로워 보이는 이 놀이에 아이들은 참여했고 이 과정을 몇 번 거치자 자연스럽게 모든 아이들이 같은 수의 사탕을 가지게 되어 소란은 종료되었다.

자기가 가진 사탕의 반을 옆에 오른쪽에 앉은 아이에게 주는 과정과 선생님이 사탕을 보충해 주는 과정을 묶어서 1 순환이라고 할 때 몇 번의 순환을 거치면 모든 아이들이 같은 수의 사탕을 가지게 되는지 계산 해보자. 단, 처음부터 홀수개의 사탕을 가지고 있으면 선생님이 짝수로 보충을 먼저 해주며 이 경우 순환수에 들어가지 않는다. 선생님은 충분한 수의 사탕을 갖고 있다고 가정하자.

입력

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각각의 테스트 케이스의 첫 줄에는 아이의 인원 N (1 ≤ N ≤ 10)이 주어지고 그다음 줄에는 각 아이들이 초기에 가지고 있는 사탕의 개수 Ci ( 1 ≤ i ≤ N, 1 ≤ Ci ≤ 30)가 주어진다. 분배 시 C1의 오른쪽에는 C2가, C2의 오른쪽에는 C3가…… 같은 식으로 앉게 되며 CN의 오른쪽에는 C1이 앉게 된다.

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대하여 모든 아이가 같은 개수의 사탕을 가질 때까지 몇 순환이 걸리는지 출력하시오.

소스코드

import sys ; r = sys.stdin.readline
for _ in range (int(r())):
    n, cnt = int(r()), 0
    C = [*map(int,r().split())]
    while True:
        C = [i if i % 2 == 0 else i + 1 for i in C]
        if len(set(C)) == 1:
            print(cnt)
            break
        C = [C[i]//2 + C[(i+1)%n]//2 for i in range(n)]
        cnt+=1

• 결과

  • 메모리 : 29284 KB
  • 시간 : 60 ms

• 문제 파악

  • 문제가 길어서 정확하게 문제를 읽고 파악하는 것이 중요한 문제로 보입니다.
  • 조건 부분을 주의해서 살펴봅니다.
    • *단, 처음부터 홀수개의 사탕을 가지고 있으면 선생님이 짝수로 보충을 먼저 해주며 이 경우 순환수에 들어가지 않는다. *
  • 모두 같은 사탕의 수를 가지는지 확인하는 부분이 필요합니다.
  • 반으로 나눈 후, 옆사람과 주고 받는 과정을 수행하는 부분이 필요합니다.

• 문제 풀이

  • 홀수인 경우에 대한 조건을 아래와 같이 작성하였습니다. 그리고 시작 전(시행 횟수를 세기 전)에 먼저 시행되어야 하므로 while문의 가장 처음 부분에서 시작하였습니다.

  • C = [i if i % 2 == 0 else i + 1 for i in C]

  • 전부 같은 숫자의 사탕을 가지는 부분은 for문을 사용할 수도 있지만, 저는 set을 사용했습니다. set함수를 적용한 후, 집합의 요소가 1개인 경우 모두 같은 수의 사탕을 가지는 것과 같습니다.

  • if len(set(C)) == 1:
                print(cnt)
                break

  • 자신의 절반과 옆 친구의 절반을 더하는 부분을 작성하였습니다. % remainder 함수를 활용해서 index가 넘어가는 경우를 다시 앞의 첫 번째인 0번이 될 수 있도록 하였습니다.

  • C = [C[i]//2 + C[(i+1)%n]//2 for i in range(n)]

  • 반복 과정을 1씩 더해주면서 총 몇 번 수행했는지 확인한 후 출력하면 됩니다.

• 문제 출처

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