글 읽기 - 어디가 틀렸는지 모르겠어요!! 반례를 알고싶습니다 ㅠㅠ

jadebaek 5년 전 0

자꾸 틀렸습니다 가 나오는데, 반례를 모르겠습니다 ㅠㅠ

이것저것 고쳐 봤는데 계속 틀렸다고 하네요...

예제로 나온 22 5, 1 2 3 4 5 => 당연히 맞습니다.
이 문제 게시글에서 찾은 예제. 1987654321 2, 15 14 => 이것도 2 잘 나옵니다.
사람 수가 놀이기구 수보다 적은 경우 => 앞에 if n<m 넣어서 해결했습니다.
5 5, 1 2 3 4 5 => 이것도 5 맞게 나옵니다.

import sys

def f_t(t, attractiontime): # f(t) = t만큼의 시간이 지났을 때, 몇 명이 놀이기구에 탑승했는가?
    result = 0;
    for i in attractiontime:
        result += (t//i)+1
    return result

def average(a, b): # 평균을 구하는 함수
    return (a+b)//2


n, m = map(int, input().split()) # 사람 수, 놀이기구 수
attractiontime = list(map(int, input().split())) # 놀이기구의 제한시간

findmin = 0
findmax = 60000000000 # 600억
t = 30000000000 # 300억

if n<m:
    print(n)
    sys.exit(1)

while(True): # 이분 탐색으로 모든 사람이 타게 되는 시간 t를 구한다.
    humans = f_t(t, attractiontime)

    if humans > n: # t가 너무 커서 전체 사람 수보다 크게 됐다.
        findmax = t
        t = average(findmin, findmax)
    elif humans < n: # t가 너무 작아서 사람이 다 타지 못했다.
        findmin = t+1
        t = average(findmin, findmax)
    if humans==n or findmin==findmax: # 적절한 시간 t를 찾았다.
        while(f_t(t, attractiontime) == f_t(t-1, attractiontime)):
            t = t-1
        for i in range(m - 1, -1, -1):
            if t % attractiontime[i] == 0:
                print(i + 1)
                break
        break

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

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠어요!! 반례를 알고싶습니다 ㅠㅠ

jadebaek 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말