글 읽기 - (파이썬) 이진법 외에 다른 풀이를 생각해봤는데 틀린 이유를 모르겠습니다.

minjyo8823 3년 전 0

제가 생각한 방법은 다음과 같습니다. (영식: x, 민식: y)

x가 항상 먼저 먹는다고 가정하면(x<y이면 x와 y의 값을 스왑) x가 첫번째 이후로 먹어야할 케이크의 양은 totalX = a/b - 1/2 이고,

i번째 순서마다 먹을 케이크의 양은 2^(-i) 입니다.

만약 2^(-i) > totalX 라면 x가 먹어야하는 양보다 더 많이 먹게 되므로 그 케이크는 y에게 주고, 아니라면 x에게 주어집니다.

이러한 과정을 계속 반복하다( x가 먹은 양/y가 먹은 양) 의 값이 처음에 입력값으로 구한 n 값과 같다면 그동안 저장한 패턴 값을 출력합니다.

이전글에서 올려주신 코드와 제 코드를 같이 돌려보면서 케이스들을 여러 개 넣어보았는데 모두 일치해서..

어느 부분에서 틀린건지 도무지 모르겠습니다....

넣은 예시들: 2 3, 4 5, 1 5, 4 9, 8 15, 107 127

from fractions import Fraction

Input = list(map(int, input().split()))
x = Fraction(Input[0], Input[1])
y = 1-x
##print(y)
if x==0: #only y eat
    print('-')
else:
    n = x/y # pattern legnth >= 2 and must include x, y

    swap = False
    if n<1: # x eat < y eat
        n = 1/n
        temp = x
        x = y
        y = temp
        swap = True
        
    pattern = '*'
    totalX = x - Fraction(1, 2)
    x = Fraction(1, 2)
    y = 0
 
    i = 1
    while len(pattern)<=60:   
        i += 1
        cake = Fraction(1, 2**i)
        if cake <= totalX:
            x += cake
            totalX -= cake
            pattern += '*'
##            print("x ", cake)
##            print(pattern)
        else:
            y += cake
            pattern += '-'
##            print("y", y)
##            print(pattern)
        if (y!=0 and x/y==n):
            break; 
    else:
        pattern = ''


    if pattern=='':
        print('-1')
    else:
       if swap:
           for i in pattern:
               if i=='*':
                   print('-', end='')
               else:
                   print('*', end='')
       else:
            print(pattern)

minjyo8823 3년 전 0

패턴 길이가 60일 때 while문을 돌고 있는 경우, break문을 통해 빠져나오면 패턴의 길이가 61인 채로 출력이 되네요..

while문의 조건을 len(pattern)<=59 으로 수정하니 됩니다.

kihun0bu 3년 전 0

영식이가 혼자만 다 먹으면 어떻게 될까요? ㅎㅎㅎ

분수가 1/1 이면 바로 오류가 나는것 같네요~

민식이가 혼자 먹는경우는 생각 하셨는데, 영식이만 먹어서 탈이 나는것 같네요

minjyo8823 3년 전 0

문제 조건에서 a와 b는 서로소이기 때문에 a/b=1이 나올수 없어서 그 경우는 제외했습니다.

pichulia 3년 전 0

1 과 1 은 서로소입니다.

그래서 1/1 은 가능한 입력 데이터입니다.

minjyo8823 3년 전 0

b는 1보다 크거나 같은 정수입니다..

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

문제

문제

출처

ICPC

(파이썬) 이진법 외에 다른 풀이를 생각해봤는데 틀린 이유를 모르겠습니다.

minjyo8823 3년 전 0

minjyo8823 3년 전 0

kihun0bu 3년 전 0

minjyo8823 3년 전 0

pichulia 3년 전 0

minjyo8823 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말