[백준] 1026번 보물 python (201011)

1. 문제 설명 

 

www.acmicpc.net/problem/1026

1026번: 보물

 

핵심은 가장 큰 수 * 가장 작은 수 로 곱해주어야, 총 합이 최소값이 나오게 된다. 

 

8 * 0

7 * 1

3 * 1

2 * 1

1 * 6

 

이렇게 밑에 줄은 내림차순, 위에 줄은 오름차순으로 정렬해서 곱해주면 최솟 값이 나옴 

 

하지만, 문제의 제약조건으로 정렬을 해서는 안된다고 한다... !! 

정렬을 해도 맞다고 정답은 뜨지만, 우선 정렬을 한 경우와 하지 않은 경우 두개다 보겠다. 

 

 

2. 풀이 

1) 정렬 한 경우 ! 정말 단순하게 접근하여 하나는 내림차순, 하나는 오름차순 정렬 후 곱하기

 

N = int(input())

all_dict = {}
for idx in range(2):
    all_dict[idx] = list(map(int,sys.stdin.readline().split()))

total_sum = 0
for a,b in zip(sorted(all_dict[0]), sorted(all_dict[1], reverse = True)):
    total_sum += (a*b)

print(total_sum)

두 리스트 입력이 딕셔너리 키 값으로 들어가게 했고 (딕셔너리 성애자) 

하나는 오름차순, 하나는 내림차순해서 zip 함수로 동시에 두 요소를 꺼내어  더해주었다.

하지만 문제의 제약조건을 어겼다. 

 

 

2) 매순간 가장 작은 수 가장 큰 수를 뽑기 (정렬은 안할 수 있음) 

 

import sys

N = int(input())

all_dict = {}
for idx in range(2):
    all_dict[idx] = list(map(int,sys.stdin.readline().split()))

total_sum = 0
for _ in range(N):
    min_idx0 = all_dict[0].index(min(all_dict[0]))
    max_idx1 = all_dict[1].index(max(all_dict[1]))
    total_sum += all_dict[0].pop(min_idx0) * all_dict[1].pop(max_idx1)

print(total_sum)

 

 

정렬을 하지 않고는 이렇게 풀 수 있다. 

매번 입력된 첫번째 리스트의 가장 작은 수와 두번째 리스트의 가장 큰 수를 뽑는 것 

매번 리스트 크기가 줄어들어서 시간 복잡도가 낮아질 수는 있겠지만, 그래도 매번 min max pop 셋다 o(n) 이라

pop 으로 리스트 길이를 줄여도 시간복잡도는 크게 줄지 않는다. 1) 번이랑 시간복잡도 비슷

 

 

단순히 정렬을 피하기 위해서 쓰는 방법인거 같다. 

 

 

3. 정리 

 

문제의 제약조건을 제발 잘 읽읍세