글 읽기 - 새해복 많이 받으세요. 이분탐색 질문드립니다.

jaa7963 2년 전 0

일단 점수를 정하고,그 점수에 따라서 그룹을 분할한뒤

더 나은 값을 찾기위해서 탐색했습니다.

그리고 리스트 컴프리헨션으로,min값을 구해서

출력했는데 틀렸다고 합니다.

4 2

1 2 3 4

ans=4

다른분이 만든 반례인 위 경우는 출력되는 것을 확인해보았습니다.

입력예시를 3개로도 나누어 보았는데, 33이라서 정상 출력되는것 같고..

어디가 문제인지 도통 알 수가 없네요.

알려주신다면 감사하겠습니다.

새해 복 많이 받으세요

from collections import defaultdict
problems,groups=map(int,input().split())

scores=list(map(int,input().split()))



def group_make(score):
    group_nums=0
    default_score=score
    group_dict=defaultdict(list)
    
    for i in range(problems):
        default_score-=scores[i]
        
        if default_score>=0:
            group_dict[group_nums].append(scores[i])    
        if default_score<0:
            group_nums+=1
            group_dict[group_nums].append(scores[i])
            default_score=(score-scores[i])
            
    return group_dict
start=0
end=sum(scores)

while end>=start:
    
    mid=(start+end)//2
    now_made=group_make(mid)
    res_num=len(now_made)
    
    if res_num<=groups:
        respond=now_made
        end=mid-1
        
    elif res_num>=groups:
        
        start=mid+1

print(min([sum(sub_list) for sub_list in respond.values()]))

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

문제

문제

출처

ICPC

새해복 많이 받으세요. 이분탐색 질문드립니다.

jaa7963 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말