문제 설명

• 길이가 같은 두 배열 A와B에서 서로의 원소를 1:1로 대응시켜 곱한 뒤 곱한 값을 모두 더한 최종 결과가 최소가 되도록 만들어야 합니다.

접근법

• B에 있는 수는 재배열 하면 안 된다라는 조건이 문제에 있지만, B를 재배열 했다고 풀이가 틀렸다라고 인식하지는 않습니다.
  • 문제를 쉽게 해결하는 방법은 두 배열을 각각 하나는 오름차순으로, 나머지 하나는 내림차순으로 정렬한 뒤 순차적으로 배열의 원소를 곱해 더합니다.
• 위 방법에서 A와B를 정렬한 이유는 가장 큰 수x가장 작은 수를 수행하기 위해서 입니다.
  • 정렬하지 않고 max와min을 통해 가장 큰 수와 가장 작은 수를 구할 수 있습니다.

정답

쉬운 풀이

N = int(input())
A = list(map(int,input().split(' ')))
B = list(map(int,input().split(' ')))

#A와B를 다르게 정렬합니다
A.sort()
B.sort(reverse=True)

answer = 0
for a,b in zip(A,B):#zip(A,B)를 하면 a에는 A의 원소가 b에는 B의 원소가 순차적으로 담깁니다.
    answer+=a*b
    
    
print(answer)

조건을 지킨 풀이

N = int(input())
A = list(map(int,input().split(' ')))
B = list(map(int,input().split(' ')))

#max(A): A에서 가장 큰 값을 리턴합니다
#A.index(값): 리스트 A에서 값이 몇번 째 위치에 있는지를 알려줍니다
#A.pop(index): 리스트 A에서 index번째 값을 A에서 제외시킨 후 해당 값을 반환합니다

answer = 0
for _ in range(N):
    a = A.pop(A.index(max(A)))
    b = B.pop(B.index(min(B)))
    answer += a*b
print(answer)

기타

• 가장 큰 수와 가장 작은 수의 곱의 합은 왜 최솟값을 보장할까?
  • 그리디 알고리즘 적인 측면이 아닐까? [99,98,1]과 [2,3,4]이 있을 때 99의 입장에서는 뒤에 있을 98과1은 신경쓰지 않고 당장 자신이 무조건 2와 곱해져야 가장 작아진다.
    • 하지만 그리디 알고리즘을 활용하기 위해서는 앞선 선택이 이후 선택에 영향을 주지 않는다라는 조건과 부분 해결 방법이 전체 해결 방법과 일치한다라는 조건이 성립해야 한다. 위 문제는 99가 2를 대리고 나가면 다음 98은 2를 선택하지 못하기 때문에 앞선 선택이 이후 선택에 영향을 준다고 봐야 할 거 같다.
      -> 그리디 알고리즘은 아닌듯, 근데 뭔가 비슷하게 느껴짐.