[n1026] 보물 in python

처음 생각해냈던 풀이는

시간초과가 났다.

 

백트래킹 방식으로 풀어봤는데

모든 경우의 수를 탐색해서 그런가보다 :( 

그래도 ide에서 돌리면 값은 나오긴 하지만

시간 초과 문제를 해결해야

정답을 인정받을 수 있으므로 다른 방식으로 코드를 작성했다.

 

# n = int(input())  # n<=50
# a = list(map(int, input().split()))  # 원소<=100
# b = list(map(int, input().split()))  # 원소<=100
# visited = [0 for _ in range(n)]
# answer = []
#
#
# # S의 값을 최소화하기 위해 A의 수를 재배열하자. S의 최솟값 출력하기
# def s(new_a):  # 점화식함수
#     temp = 0
#     for i in range(n):
#         temp += new_a[i] * b[i]
#     return temp
#
#
# def func(depth, new_a):
#     if depth == n:
#         answer.append(s(new_a))
#         return
#     for i in range(n):
#         if visited[i]:  # 방문한 적이 있다면?
#             continue
#         visited[i] = 1
#         new_a.append(a[i])
#         func(depth + 1, new_a)
#         visited[i] = 0
#         new_a.pop()
#
#
# func(0, [])
# print(min(answer))

---

홈페이지에 힌트가 나와있는 걸 보았다.

>> A를 {1, 1, 0, 1, 6}과 같이 재배열하면 된다.

즉, a의 가장 작은 값과 b의 가장 큰 값을 찾아 곱해주면

s의 최소값을 구할 수 있다.

 

n = int(input())  # n<=50
a = list(map(int, input().split()))  # 원소<=100
b = list(map(int, input().split()))  # 원소<=100
answer=0

for _ in range(n):
    answer+=min(a)*max(b)
    a.pop(a.index(min(a)))
    b.pop(b.index(max(b)))

print(answer)