728x90
문제
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.
코드
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
answer_list = ['0' for i in range(N)]
copy_b = B.copy()
for i in range(0, N):
a_min_idx = A.index(min(A))
b_max_idx = copy_b.index(max(copy_b))
answer_list[b_max_idx] = A[a_min_idx]
A[a_min_idx] = 101
copy_b[b_max_idx] = -1
answer = 0
for i in range(0, N):
answer += answer_list[i] * B[i]
print(answer)
설명
- 문제이름 및 번호: 보물(1026번)
- 시간복잡도: O(N)
- 관련 알고리즘: 그리디 알고리즘
- B 배열의 순서는 그대로 두고, A배열만 순서를 바꾸어 각 인덱스끼리 곱하여 합했을 때 최소값을 구해야 한다
- 이를 위해서는 B 배열에 있는 최대값들을 가장 많이 줄이기 위해 A 배열의 최소값 순서대로 곱해주면 된다
- 따라서 B 배열의 최대값 목록을 A 배열의 최소값 순서에 따라 곱해주었다
- 그리디 알고리즘에 따라 직관적으로 떠오른 아이디어는 좋았던 것 같으나, N 길이의 for문을 2번 돌았던 점이 아쉽다
- 또한 입력 리스트와 동일한 길이의 리스트를 2개나 더 생성해서, 메모리 측면에서 낭비가 좀 있었던 것 같다
- 이를 최소화할 수 있도록 고민해보면 좋을 것 같다
728x90
'Dev > BAEKJOON 백준' 카테고리의 다른 글
[백준/BOJ] 백준 코딩 알고리즘 11729번 하노이 탑 이동 순서/Python (1) | 2023.07.12 |
---|---|
[백준/BOJ] 백준 코딩 알고리즘 2447번 별 찍기 - 10/Python (0) | 2023.07.11 |
[백준/BOJ] 백준 코딩 알고리즘 1935번/Python (0) | 2022.10.07 |
[백준/BOJ] 백준 코딩 알고리즘 11049번/C++ (0) | 2019.07.26 |
[백준/BOJ] 백준 코딩 알고리즘 11051번/C++ (0) | 2019.07.26 |