[Algorithm] [Python] 백준/BOJ - 1026 보물

1026 보물

---

문제

---

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 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의 최솟값을 출력한다.

제출 코드

---

import sys

N = int(input())
A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))
result = 0
for _ in range(N):
   result += A.pop(A.index(min(A))) * B.pop(B.index(max(B)))
print(result)

코드 설명

---

이 문제의 핵심은 조건 제한에 따른 조합이다.

배열 B는 재배열 하면 안된다는 조건이 있었고 오직 A 배열만 재배열 하여 A[i] * B[i] 값의 합을 최소화 하여야한다.

두 배열로 부터 뽑아낸 정수와 정수의 곱을 최소화 하기 위해서는 한 배열의 최대값은 한 배열의 최소값을 곱하는 방식을 이용해야 한다고 생각했다.

길이 N을 입력받고 배열 A,B의 원소들을 입력받음과 동시에 int로 type casting을 위해 map내장 메서드를 이용하여 list 배열을 만들었다.

그 이후, 결과값을 담을 result 변수를 초기화 한 뒤, 배열의 길이만큼 반복을 진행한다.

result += A.pop(A.index(min(A))) * B.pop(B.index(max(B)))

위 한 줄이 핵심이다.

A 배열 내 최소값을 뽑아내기 위하여 배열의 index값을 인자로 받는 pop()메서드를 사용하되 인자값을 맞춰주기 위하여 해당 원소에 대한 index값을 반환하는 index()메서드 그리고 그 인자로 min()내장 함수를 사용하여 배열 내 최소값을 찾아냈다.

B 배열 또한 위와 같은 로직으로 진행하여 최대값을 뽑아냈다.

그렇게 각각 배열에서 최소값과 최대값을 pop()한 뒤 곱하여 result변수에 더해주는 방식으로 반복한 뒤 해당 값을 출력했다.

부가 설명

---

문제를 푼 뒤, 다른 사람들의 코드를 확인하기 위하여 구글링 해봤는데 몇몇 블로그의 글 들은

제한조건을 어겨서 B배열을 재배열 하여 문제를 푼 경우가 많았다.

근데 웃긴건, 조건에 명시되어 있음에도 불구하고 judge site에서 정답이라는 결과가 나온다는 것이다...ㄷ

그 외에는 대체로 나와 비슷한 코드의 흐름이였다.