글 읽기 - python 으로 풀었는데 반례를 모르겠습니다.

turtle1990 1년 전 0

다른분들에 비해 제가 좀 지저분하게 풀었습니다

일단 예시에 대한 정답은 나오는데 반례를 질문게시판을 참조해도 못찾겠어서 글을 올립니다.

N,M = list(map(int,input().split()))
B_input = list(map(int,input().split()))
B_input.sort()
B_input.reverse()
def cal_best(M,B):
    ls_SUM_best=[]
    ls_SUM_NEW=[]
    F_END=False
    for i1,VAL in enumerate(B):
        if F_END==True:
                break
        if VAL<M:
            if len(ls_SUM_NEW)>0:
                ls_SUM_NEW[0]=VAL
            else:
                ls_SUM_NEW.append(VAL)
            for i2 in range(len(B[i1+1:])):
                if F_END==True:
                    break
                VAL2=B[i1+i2+1]
                if VAL+VAL2<M:
                    if len(ls_SUM_NEW)>1:
                        ls_SUM_NEW[1]=VAL2
                    else:
                        ls_SUM_NEW.append(VAL2)
                for i3 in range(len(B[i1+i2+2:])):
                    VAL3=B[i1+i2+i3+2]
                    if VAL+VAL2+VAL3<M:
                        if len(ls_SUM_NEW)==3:
                            ls_SUM_NEW[-1]=VAL3
                        else:
                            ls_SUM_NEW.append(VAL3)
                        if sum(ls_SUM_NEW) > sum(ls_SUM_best):
                            del ls_SUM_best[:] 
                            ls_SUM_best+=ls_SUM_NEW
                        ls_SUM_NEW=[]
                        break
                    elif VAL+VAL2+VAL3==M:
                        if len(ls_SUM_NEW)==3:
                            ls_SUM_NEW[-1]=VAL3
                        else:
                            ls_SUM_NEW.append(VAL3)
                        del ls_SUM_best[:]
                        ls_SUM_best+=ls_SUM_NEW
                        F_END==True
                        ls_SUM_NEW=[]
                        return ls_SUM_best
    return ls_SUM_best

ls_SUM_best=cal_best(M,B_input)
print(sum(ls_SUM_best))

vyu 1년 전 1

반례 드리겠습니다

이하는 원활한 확인을 위해 약간의 print()문을 추가해서 실행해본 결과입니다 :)

-------------------------------------------------------------------------------------------------

5 37
20 12 10 7 2
ls_SUM_NEW(#1 - 2) : [20]
ls_SUM_NEW(#2 - 2) : [20, 12]
each index : 0 1 2
each index : 0 1 3
each index : 0 1 4
ls_SUM_NEW(#3 - 2) : [20, 12, 2]
ls_SUM_BEST(#3) : [20, 12, 2]
ls_SUM_NEW(#2 - 2) : [10]
each index : 0 2 3
ls_SUM_NEW(#4) : [10, 7]
ls_SUM_BEST(#4) : [10, 7]
17

# 본래 정답 : 37 ( 20 + 10 + 7 )

N, M = list(map(int,input().split()))
B_input = list(map(int,input().split()))
B_input.sort()
B_input.reverse()
# B_input.sort(reverse=True)
# print("B : ", B_input)
def cal_best(M,B):
    ls_SUM_best=[]
    ls_SUM_NEW=[]
    F_END=False
    for i1,VAL in enumerate(B):
        if F_END==True:
            print("end !")
            break
        if VAL<M:
            if len(ls_SUM_NEW)>0:
                ls_SUM_NEW[0]=VAL
                print("ls_SUM_NEW(#1 - 1) : ", ls_SUM_NEW)
            else:
                ls_SUM_NEW.append(VAL)
                print("ls_SUM_NEW(#1 - 2) : ", ls_SUM_NEW)
            for i2 in range(len(B[i1+1:])):
                if F_END==True:
                    break
                VAL2=B[i1+i2+1]
                if VAL+VAL2<M:
                    if len(ls_SUM_NEW)>1:
                        ls_SUM_NEW[1]=VAL2
                        print("ls_SUM_NEW(#2 - 1) : ", ls_SUM_NEW)
                    else:
                        ls_SUM_NEW.append(VAL2)
                        print("ls_SUM_NEW(#2 - 2) : ", ls_SUM_NEW)
                for i3 in range(len(B[i1+i2+2:])):
                    print("each index : ", i1, i1+i2+1, i1+i2+i3+2)
                    VAL3=B[i1+i2+i3+2]
                    if VAL+VAL2+VAL3<M:
                        if len(ls_SUM_NEW)==3:
                            ls_SUM_NEW[-1]=VAL3
                            print("ls_SUM_NEW(#3 - 1) : ", ls_SUM_NEW)
                        else:
                            ls_SUM_NEW.append(VAL3)
                            print("ls_SUM_NEW(#3 - 2) : ", ls_SUM_NEW)
                        if sum(ls_SUM_NEW) > sum(ls_SUM_best):
                            del ls_SUM_best[:]
                            ls_SUM_best+=ls_SUM_NEW
                            print("ls_SUM_BEST(#3) : ", ls_SUM_best)
                        ls_SUM_NEW=[]
                        break
                    elif VAL+VAL2+VAL3==M:
                        if len(ls_SUM_NEW)==3:
                            ls_SUM_NEW[-1]=VAL3
                        else:
                            ls_SUM_NEW.append(VAL3)
                        del ls_SUM_best[:]
                        ls_SUM_best+=ls_SUM_NEW
                        print("ls_SUM_NEW(#4) : ", ls_SUM_NEW)
                        print("ls_SUM_BEST(#4) : ", ls_SUM_best)
                        F_END==True # == ?
                        ls_SUM_NEW=[]
                        return ls_SUM_best
    return ls_SUM_best

ls_SUM_best=cal_best(M,B_input)
print(sum(ls_SUM_best))

turtle1990 1년 전 1

감사합니다 ~ 문제점을 찾았네요

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

문제

문제

출처

ICPC

python 으로 풀었는데 반례를 모르겠습니다.

turtle1990 1년 전 0

vyu 1년 전 1

turtle1990 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말