[Python] 백준 1026 - 보물

https://www.acmicpc.net/problem/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의 최솟값을 출력한다.

---

해결방법

파이썬의 내장함수를 이용하는 방법이 가장 쉬울 것 같습니다. 직접 각 배열 안에 최소, 최대 원소의 인덱스를 구하는 함수를 구현할까 했지만 직접 구현한 것보단 내장함수를 이요하는 것이 더 빠를 거라 생각했습니다. 또한 반복문을 이용해도 괜찮겠지만 저는 재귀함수를 이용해서 풀이해봤습니다.

 

def S(A:list, B:list, ans):
  if A==[] or B==[]:
    return ans
  else:
    idx_A = A.index(min(A))
    idx_B = B.index(max(B))
    ans += A.pop(idx_A) * B.pop(idx_B)
    return S(A, B, ans)

_ = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
print(S(A,B,0))

 

코드 설명

재귀함수를 통해 이 문제를 해결하고 있습니다. 따라서 처음 배열의 길이를 입력해준 것은 사용하지 않습니다.

S 함수에 대한 설명을 하겠습니다.

S 함수는 매개변수가 A, B 리스트, ans (int)입니다. 만약 A 또는 B 리스트의 길이가 0이 되면 ans라는 결과를 반환합니다. 그렇지 않으면 아래에 else 문을 돌 것입니다.

idx_A 는 A 리스트에서 최솟값의 인덱스입니다. 반대로 idx_B 는 B 리스트에서 최댓값의 인덱스입니다.

각 리스트에 pop(idx)을 하며 동시에 ans에 최솟값과 최댓값의 곱을 더해줍니다. 그리고 다시 재귀함수를 실행합니다.

S 함수가 실행이 다 되면 결과를 출력하는 것입니다.