[백준 - 1026][Python] 보물

안녕하세요 성조입니다.

이번 포스팅은 Python 3 버전으로 풀이됐습니다.

 

문제를 읽어보면 직관적으로 풀기 쉬운 문제라고 생각합니다.

 

 

 

문제 출처

https://www.acmicpc.net/problem/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(sys.stdin.readline())

A_list = list(map(int, sys.stdin.readline().split()))
B_list = list(map(int, sys.stdin.readline().split()))

S = 0

A_list.sort()

for i in range(N):
    S += (max(B_list) * A_list[i])
    B_list.remove(max(B_list))

print(S)

 

풀이

최대한 읽기 쉬운 코드로 작성했다.

 

[접근 방법]

1. N의 길이를 입력받는다.

2. A, B를 파이썬에서 지원하는 리스트 타입으로 입력받는다.

3. A는 정렬이 가능하고, B는 정렬이 안되므로 A만 내림차순으로 정렬한다.

4. A와 B는 N의 길이 만큼 입력 받을 수 있기 때문에 N번 만큼 반복한다.

5. B의 가장 큰 값과 A의 가장 작은 값을 곱한다. 이후 S에 더한다.

6. B의 가장 큰 값을 제거하고, B의 다음 큰 값과 A의 다음 작은 값을 서로 연산하고 반복한다.

7. 합산된 S를 출력한다.

 

 

---

오타나 이해가 안가는 부분이 있다면 언제든지 댓글로 얘기해 주시면 감사드리겠습니다.

 

 

 

다음 포스팅 때 뵙겠습니다.