글 읽기 - 반례 부탁드립니다 ..(틀렸습니다!)

ba2soon 2년 전 0

~~2%에서 틀렸다고뜹니다..ㅠㅠ~~

우선 입력값의 비율 다 약분해주고

사슬처럼 연쇄될 수 있도록 데이터 정렬해주었습니다.

0 2 1 1

1 3 1 1

0 1 1 1

이면

0 2 1 1

0 1 1 1

1 3 1 1

이 되도록 연속한 두 데이터에는 같은 재료가 있도록 정렬하였습니다.

이후 총 비율을 담을 리스트를 만들고 전부 0으로 초기화한 다음

데이터 길이만큼 반복문 돌리면서

비율리스트 최신화시키는 느낌으로 코드 짜봤습니다.

이 때 약분도 다 되도록 나름의 수학적인 계산을 통해 코드를 썼습니다.

반례 부탁드립니다..

def gcd(a, b):
  while (b != 0):
    temp = a % b
    a = b
    b = temp
  return abs(a)

N = int(input())
data = [list(map(int, input().split())) for _ in range(N-1)]

for i in range(N-1):
  gcd_result = gcd(data[i][2], data[i][3])
  data[i][2] //= gcd_result
  data[i][3] //= gcd_result

for i in range(len(data)):
  for j in range(i+1, len(data)):
      if data[i][0] == data[j][0] or data[i][0] == data[j][1]:
        data[i+1], data[j] = data[j], data[i+1]
        break
      if data[i][1] == data[j][0] or data[i][1] == data[j][1]:
        data[i+1], data[j] = data[j], data[i+1]
        break
        
ratio = [0] * N
ratio[data[0][0]] = data[0][2]
ratio[data[0][1]] = data[0][3]

for i in range(1, len(data)):
  if ratio[data[i][0]] != 0 and ratio[data[i][1]] != 0:
    pass
  elif ratio[data[i][0]] != 0:
    ratio[data[i][1]] = data[i][3]*ratio[data[i][0]]
    for j in range(len(ratio)):
      if j == data[i][1]:
        pass
      else:
        ratio[j] *= data[i][2]
    gcd_result = gcd(ratio[data[i][0]]//data[i][2], data[i][2])
    if gcd_result != 1:
      for j in range(len(ratio)):
        ratio[j] //= gcd_result 
  elif ratio[data[i][1]] != 0:
    ratio[data[i][0]] = data[i][2]*ratio[data[i][1]]
    for j in range(len(ratio)):
      if j == data[i][0]:
        pass
      else:
        ratio[j] *= data[i][3]
    gcd_result = gcd(ratio[data[i][1]]//data[i][3], data[i][3])
    if gcd_result != 1:
      for j in range(len(ratio)):
        ratio[j] //= gcd_result 
  else:
    print("Input Error")

for i in range(len(ratio)):
  if i == len(ratio)-1:
    print(ratio[i], end="")
  else:
    print(ratio[i], end=" ")

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁드립니다 ..(틀렸습니다!)

ba2soon 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말