[코테/백준] Python 보물 - 1026번

성공 | 시도 2번

 

🔗 [백준] 1026번 보물

1026 : [그리디 알고리즘] 보물(py)

---

문제 설명

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

---

출력

첫째 줄에 S의 최솟값을 출력한다.

---

입력과 출력 예시

입력	출력
5 1 1 1 6 0 2 7 8 3 1	18
3 1 1 3 10 30 20	80
9 5 15 100 31 39 0 0 3 26 11 12 13 2 3 4 5 9 1	528

 

---

내 소스

# 통과는 되지만 조건은 어긴 풀이
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort(reverse=True)
b.sort()

result = 0
for i in range(n):
    result += a[i] * b[i]
print(result)

- 작은 수를 만들기 위해서 배열 A는 내림차순, 배열 B는 오름차순으로 정렬하였다. (반대로 A 오름차순, B 내림차순해도 상관없다) 이유는 A의 작은 수와 B의 큰 수, A의 큰 수와 B의 작은수를 곱해야 작은 수를 만들 수 있기 때문이다.

- 'B에 있는 수는 재배열하면 안된다.'는 조건을 까먹고 코드를 작성했다. 위 코드를 제출해도 운좋게 통과되었지만 제대로 할 필요가 있어서 다시 풀어보았다. 

 

# 조건을 지킨 풀이
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

result = 0
for i in range(n):
    result += min(a) * max(b)
    a.remove(min(a))
    b.remove(max(b))
print(result)

 

소스 설명

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

[1 - 3] : 배열의 길이와 배열들을 각각 입력받아 n, a, b에 저장한다.

 

result = 0
for i in range(n):
    result += min(a) * max(b)
    a.remove(min(a))
    b.remove(max(b))

[5 - 9] : min()과 max() 함수를 이용해서 배열 A의 작은 수와 배열 B의 큰 수를 곱한다. 그 후, 배열 A의 작은 수와 배열 B의 큰 수를 각 리스트에서 제거한다. (그 다음으로 배열 A의 작은 수와 배열 B의 큰 수를 곱하기 위함이다.)

---

다른 코드 분석

- pop과 index 함수를 사용하여 각 리스트에서 작은 값과 큰 값을 제거하였다. [1]

- A 리스트만 오름차순으로 정렬하고 B 리스트에서 가장 큰 값을 갖는 원소를 pop()으로 꺼내서 A 리스트의 원소와 곱해준다. [2] 

 

---

회고

- 처음 문제를 풀었을 때 조건을 어겨도 운좋게 통과되었지만 다음부터는 문제를 재대로 읽고 풀어야겠다는 생각을 하게 되었다.

---

Ref. 

1. 문제 풀이 / https://yoonsang-it.tistory.com/44

2. 문제 풀이 / https://gudwns1243.tistory.com/55

3. 문제 풀이 / https://velog.io/@zwooo96/%EB%B0%B1%EC%A4%80-1026%EB%B2%88-%EB%B3%B4%EB%AC%BC-%ED%8C%8C%EC%9D%B4%EC%8D%ACPython

---

* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀