[BOJ] 9037 - The candy war

사용 언어: Python3

문제

백준 9037

코드

내 풀이

def splitCandies(i, candies, tmp):
  if candies[i] % 2 != 0:
      candies[i] += 1
  tmp[i] = candies[i] // 2 # 반 떼어서 tmp에 저장

def deliverCandies(i, candies, tmp):
  candies[i] -= tmp[i] # 내꺼 차감
  candies[(i+1) % len(candies)] += tmp[i] # 옆 친구꺼 추가

T = int(input()) # 테스트 케이스 수
ans = [0 for _ in range(T)] # 테스트케이스마다 시도 횟수들 저장

for t in range(T):
  N = int(input()) # 아이의 인원 N
  candies = [x for x in list(map(int, input().split()))] # 각 아이들이 초기에 가지고 있는 사탕의 개수
  tmp = [0 for _ in range(N)] # 각 아이들이 반 떼어서 보관해놓을 공간
  cnt = 0 # 모든 아이가 같은 개수의 사탕을 가질 때까지 시도 횟수

  # 반 떼어서 주기 게임 반복
  while len(set(candies)) > 1:
    tmp = [0 for _ in range(N)]
    cnt += 1

    # 반 떼어내기
    for i in range(N):
      splitCandies(i, candies, tmp)

    # 옆 친구한테 주기
    for i in range(N):
      deliverCandies(i, candies, tmp)

  ans[t] = cnt

# output
for x in ans:
  print(x)

• 답이 다르게 나온다..

내 풀이 - 3/30 추가

# 사탕 절반을 옆 친구한테 전달
def deliverCandies(N, candies):
  half = [0 for _ in range(N)] # 절반을 떼어놓을 리스트

  # 절반 떼기
  for i in range(N):
    if candies[i] % 2 == 1:
      candies[i] += 1
    candies[i] //= 2
    half[i] = candies[i]

  # 오른쪽으로 전달 (왼쪽 친구한테 받음)
  for i in range(N):
    candies[i-1] += half[i]

  return candies

def process():
  N = int(input())
  candies = list(map(int, input().split()))
  cnt = 0

  # 단, 처음부터 홀수개의 사탕을 가지고 있으면 선생님이 짝수로 보충을 먼저 해주며 이 경우 순환수에 들어가지 않는다.
  for i in range(N):
    if candies[i] % 2 == 1:
      candies[i] += 1
  
  while True:
    candies = deliverCandies(N, candies) # 갱신
    cnt += 1
    if len(set(candies)) == 1:
      print(cnt) # output
      break
    # cnt += 1

T = int(input())
for _ in range(T):
  process()

• 답이 +1 씩 되어서 나온다…

다른 풀이

# 모든 아이들이 가지고 있는 사탕수가 동일한지 체크
def check(N, candies):
  # 홀수라면 짝수로 만들어서 체크
  for i in range(N):
    if candies[i] % 2 != 0:
      candies[i] += 1
  
  return len(set(candies)) == 1

# 반 잘라서 옆 친구한테 전달
def deliverCandies(N, candies):
  tmp = [0 for _ in range(N)] # 각 아이들이 반 떼어서 보관해놓을 공간
  for i in range(N):
    if candies[i] % 2 != 0:
      candies[i] += 1
    tmp[(i+1)%N] = candies[i]//2
    candies[i] //= 2 # 내꺼 절반으로 나누기

  for i in range(N):
    candies[i] += tmp[i]

  return candies # 갱신된 배열 반환

def process():
  # N은 학생 수
  N, candies = int(input()), list(map(int, input().split()))
  cnt = 0
  while not check(N, candies): # candies가 다 같지 않은동안 반복
    cnt += 1
    candies = deliverCandies(N, candies)
    # 여기서는 수가 작아서 배열을 갱신하는 방법을 사용했지만, 수가 커진다면 시간복잡도가 늘어나니 global로 변경 가능
  print(cnt)
    

T = int(input())
for _ in range(T):
  process()

또 다른 풀이

def process():
  N = int(input())
  candies = list(map(int, input().split()))
  tmp = [0] * N
  cnt = 0 # 회전수
  
  while True:
      for i in range(N):
          if candies[i] % 2:
              candies[i] = candies[i] + 1
          tmp[i] = candies[i] // 2

      if len(set(candies)) == 1: # ✅ set()을 이용해 리스트가 모두 같은 원소로 이루어졌는지 확인할 수 있다!
          print(cnt) # 회전수 출력
          break

      for i in range(1, N):
          candies[i] = candies[i] // 2 + tmp[i-1] # 내꺼 절반 + 왼쪽 친구꺼 절반(tmp[i-1])
      candies[0] = candies[0] // 2 + tmp[-1] # 0번째 친구는 맨 마지막 친구가 준다

      cnt += 1

T = int(input())
for _ in range(T):
  process()

• 가장 간결한 풀이이다.
• check() 메서드를 따로 만들지 않고 break 문으로 빠져나갈 수도 있다. (무한루프 주의)
• 오른쪽 친구한테 준다는 말은 왼쪽 친구한테 받는다는 말과 같다!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기