📝 문제 설명
>
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/1026
🎨 풀이
💡 전체 코드
import sys
n = int(input())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
result = 0
A.sort()
for i in range(n):
result += A[i] * max(B)
B.remove(max(B))
print(result)
> 핵심 : 최솟값을 구하려면 작은 값 * 큰 값 이런식으로 곱해주면 됨. 예를 들면, A=[1,7] , B=[7,4] 라면 1 * 7 + 7 * 4 = 35 가 최솟값임. 만약 7 * 7 을 하게 두면 수가 엄청 커져버림. A는 정렬해두고, B에서 필요한 거 뽑아서 곱해주면 됨. (B는 정렬 불가라고 적혀있어서!)
🍦 코드 설명 (실행 순서대로 나열)
# main
n = int(input())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
1. n을 입력받는다.
- n : 한 리스트에 들어있는 숫자 수
2. A, B를 입력받는다.
- A,B : n개의 수가 들어있는 리스트
result = 0
A.sort()
3. result 변수를 초기화한다.
- result : S의 최솟값
4. A를 오름차순으로 정렬한다.
@ 첫 번째 for문 (3번~5번) => 동전 종류 입력받기
for i in range(n):
result += A[i] * max(B)
B.remove(max(B))
3. for문을 돌린다. (n만큼)
4. A[i] 와 B의 max값을 곱한 후, 그 값을 result에 더해준다.
- A의 작은 값과 B의 큰 값을 곱해주는 것임.
5. B 리스트에서 max(B) 값을 삭제한다.
6. result를 출력한다.
끝~
⭐ 느낀점
> 처음에는 이게 B를 정렬해도 되는 줄 알고 reversed=True를 써서 풀었는데, 이 글 적으려고 보니까 문제에 "B에 있는 수는 재정렬하면 안된다" 가 적혀있었다. ㅎㅎ.. 문제 꼼꼼히 읽기를 좀 해야할듯하다. 그리고 잘 풀었다고 생각한다. 잘했다~
'알고리즘 공부 > 백준' 카테고리의 다른 글
[백준] 10870번 - 피보나치 수 5 (파이썬) (0) | 2022.07.27 |
---|---|
[백준] 10872번 - 팩토리얼 (파이썬) (0) | 2022.07.26 |
[백준] 11047번 - 동전 0 (파이썬) (0) | 2022.07.24 |
[백준] 1003번 - 피보나치 함수 (파이썬) (0) | 2022.07.23 |
[백준] 11399번 - ATM (파이썬) (0) | 2022.07.22 |