글 읽기 - 파이썬 17374 실패 질문

kjmin2000 1년 전 0

코인이나 비트 중 하나로 전부 교환을 해줍니다(가능한 만큼, 저는 비트로 교환했습니다.)

그 후 비트의 값을 줄이고, 코인의 값을 늘려나가며 그 차이가 최소가 되는 순간을 구했습니다.

어디서 문제가 있는 걸까요?

# ---------- Import ----------
import sys
input = sys.stdin.readline

# ---------- Function ----------
def bitcoin():
    global coin
    
    coin += (Q // C) * D	# 베리를 코인으로 교환
    coin += (P // A) * B	# 비트를 코인으로 교환
    bit = P % A				# 코인으로 교환하고 남은 비트
    
    ans = 1e9
    while coin > 0:
        coin -= B	# 코인 교환비만큼 감산
        bit += A	# 비트 교환비만큼 가산
        dif = abs(bit - coin)	# 코인과 비트의 개수 차이
        
        if dif < ans:
            ans = dif
            
        if dif > ans:	# dif가 줄어들다 늘어나는 지점이 최소 차이 순간
            coin += B	# 이전 반복에서 최소이므로
            bit -= A	# 이전 반복에서 최소이므로
            
            return min(bit, coin)
        
    return 0

# ---------- Main ----------
caseT = int(input())
coin = 0

for _ in range(caseT):
    P, Q, A, B, C, D = map(int, input().split())
    # P비트, Q베리, A:B=비트:코인, C:D=베리:코인
    
    print(bitcoin())
    
# ---------- Comment ----------
# 비트나 코인 중 하나를 기준으로 잡고 연산을 실행

dh0450 1년 전 1

코인이 1개 비트가 1개가 있고 A = 10, B = 10 이라고하면

처음 while 문이 돌면서 coin 이 0보다 작아지고 두번째 루프를 돌 수 없습니다.

그리고 이런 반복문을 통한 접근은 A = 1, B = 10000 같은 돈복사 비율이 있는 경우 시간초과가 납니다.(T 가 1000 )

다른 방법을 탐구하셔야합니다.

kjmin2000 1년 전 0

이 방법은 시간 초과를 감안하고 우선 작성해본 코드입니다!

틀렸습니다와 시간 초과 중에서 틀렸습니다가 먼저 나오는 걸로 알고 있습니다.

시간 초과가 발생하는 경우에는 문제 접근은 맞았으나, 효율적인 코드 진행을 해야 하는 것이 맞는데

제 제출에서는 틀렸습니다가 찍혀 나와 '아 이건 애초에 틀린 알고리즘이구나'라고 생각했습니다!

시간 초과가 나기에 다른 방법을 탐구해야 하는 게 맞습니다.

하지만 그 전에 제가 작성한 코드가 무엇 때문에 틀렸는지 궁금합니다 ㅠㅠ

dh0450 1년 전 1

틀린이유는 위에 말씀드렸는데..

kjmin2000 1년 전 0

아아 죄송합니다!

2번째 루프를 돌지 못할 시 당연히 값이 나오지 않아 틀린다는 걸

너무 시간 초과에 집착해서 그게 시간 초과라고 혼동해버렸네요

감사합니다 다른 방법을 생각해서 풀었습니다 :)

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

문제

문제

출처

ICPC

파이썬 17374 실패 질문

kjmin2000 1년 전 0

dh0450 1년 전 1

kjmin2000 1년 전 0

dh0450 1년 전 1

kjmin2000 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말