글 읽기 - [파이썬] 맞았는데 궁금한 점이 있습니다.

kckc0608 4년 전 0

처음엔 단순하게 3개의 수를 뽑는 조합을 생각해서 모든 케이스를 돌려보자고 생각했으나, 3개의 수를 뽑는 조합을 알고리즘으로 구현을 못하겠더라구요..

그래서 떠올린 아이디어가 세수를 n1, n2, n3 이라고 하면,

n1 + n2 + n3 <= m

n1 + n2 <= m - n3

이렇게 조건을 바꿔 생각해보았습니다. 두 수의 합과 관련하여 모든 경우의 수를 체크하는 알고리즘은 이미 아이디어가 있었거든요

(1 2 3 4 가 있다면 / 1+2, 1+3, 1+4 / 2+3, 2+4 / 3+4 / 이렇게 왼쪽에 있는 수보다 큰 수만을 오른쪽에 더하여 구하는 아이디어를 떠올렸습니다. 그래서 정렬도 했습니다)

처음엔 이 아이디어를 알고리즘으로 구현하되, 만약 n1 + n2 + n3 == m 인 순간이 나오면, 굳이 모든 케이스를 검사할 필요가 없으니 break 로 루프를 빠져나가자고 생각했습니다.

그런데 틀렸다고 나오더군요

질문글을 쓰려고 들어갔다가 FAQ를 보고 break 를 모두 지웠더니 정답이 되었습니다.

n1+n2+n3 = m 이 된 순간이 되면, 세수의 합이 결국 최대가 된 순간이니 그 순간을 출력하면 break 를 쓰더라도 맞을 텐데 왜 틀렸다고 나왔던 건지 궁금합니다.

(기존 틀렸던 코드에서 예시 1의 5 21 입력 후 5 6 7 8 9 를 입력했을 때 21이 제대로 나왔었습니다.)

####### 틀렸던 코드 #######
n,m = map(int,input().split(' ')) #n장의 카드 중에 M 이하의 수를 만들어야함.
num = list(map(int,input().split(' ')))
num.sort()
_sum = 0
find = False
k = 0
level = 0 # 기준
while k < n:
    level = m-num[k]
    for i in range(n-1): #0~n-2 //0~3
        if i == k: # k는 이미 꺼낸 카드이므로 두 수의 합에 사용될 카드가 될 수 없음
            continue
        else:
            for j in range(i+1,n):
                if j == k:
                    continue
                else:
                    if num[i] + num[j] <= level:
                        if num[k] + num[i] + num[j] > _sum:
                            _sum = num[k] + num[i] + num[j]
                    if num[i] + num[j] == level:
                        find = True
                        break # j에 대한 반복문 나감.
                    else:
                        break
        if find == True:
            break
        
    if find == True:
        break
    k+=1
        
print(_sum)

###### FAQ를 읽고 break를 없앤 정답이 된 코드 #######
n,m = map(int,input().split(' ')) #n장의 카드 중에 M 이하의 수를 만들어야함.
num = list(map(int,input().split(' ')))
num.sort()
_sum = 0
k = 0
level = 0 # 기준
while k < n:
    level = m-num[k]
    for i in range(n-1): #0~n-2 //0~3
        if i == k:
            continue
        else:
            for j in range(i+1,n):
                if j == k:
                    continue
                else:
                    if num[i] + num[j] <= level:
                        if num[k] + num[i] + num[j] > _sum:
                            _sum = num[k] + num[i] + num[j]
                    else:
                        break
    k+=1
        
print(_sum)

blpoms 4년 전 1

틀린코드에서 25, 26줄 지우니 통과됐습니다.

kckc0608 4년 전 0

25, 26줄에서 막은게 있었나보네요.. 한번 고민해보겠습니다! 감사합니다 :)

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