문제
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.
링크 참조
풀이 설명
입력 받은 두 개의 배열을 곱했을 떄 가장 작게 나오는 S을 구하면 된다.
두 개를 곱해서 더한 것이 가장 작으려면
가장 큰 값 * 가장 작은 값 으로 더할 수 있도록 하는 것이 중요하다
그렇다면 A는 내림차순, B는 오름차순으로 해서 곱해버리면 되지만
B는 재배열 하지 말라는 조건이 있다.
따라서, B을 재배열 하지 않고도 큰 값 순으로 생각할 수 있기만 하면 된다.
코드
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
newB = sorted(B,reverse=True)
A.sort()
Sum = 0
for i in range(N):
Sum += A[i] * B[B.index(newB[i])]
print(Sum)B를 재배열 할 수 없으니 B을 정렬한 새로운 리스트를 만든다. (sorted 함수 이용)
이후, A는 배열할 수 있으니 A는 오름차순으로 배열한다. ( sort() 이용 )
Sum 은 정답 값으로 이용할 것이기에 0으로 초기화 해준다.
A 리스트는 내림차순으로 작은 -> 큰 순으로 정렬되어 있다.
newB 리스트는 reversed=True 했기에 큰 -> 작은 순으로 정렬되어 있다.
i = 0 일 때로 설명해보겠다.
newB[0] 은 B 요소 중에 가장 큰 값이 담겨 있을 것이다.
따라서, B.index(newB[0]) 을 하게 되면 리스트 B의 가장 큰 값의 index을 얻게 된다.
즉, B 요소에서 가장 큰 값의 인덱스를 알 수 있게 된다.
인덱스를 알았기에, B[ 해당 인덱스 ] 를 하게 되면 값을 얻을 수 있다.
B [ B.index(newB[i]) ] 을 하게 되면 가장 큰 값을 얻을 수 있게 되는 것이다.
이를 이용하여, 배열 크기인 N만큼을 반복하며
A 리스트의 작은 값 * B 리스트의 가장 큰 값 으로 곱해진 값이 Sum에 더해지게 된다.
💌
끝으로
이 문제는 첫 번째로 풀이했던 index만 잘 쓸 줄 알면 쉽게 풀어낼 수 있었던 것 같다.
