백준 1026: 보물 Python (Greedy)

 

https://www.acmicpc.net/problem/1026

1026번: 보물

 

 

이 문제는 Greedy로 푸는데, 문제에 함정이 있다.

"S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다."라는 조건이 있는데, 사실상 A를 재배열하는 것이나 A, B를 모두 재배열하는 것이나 똑같다.

 

첫 번째. 오답

B를 재배열하지 않기 위해서 많이 돌아갔다.우선 B 배열에 대해서 B_sort, B_spare, B_index 배열들을 만들어서 원소와 인덱스를 합친다. 이때, 인덱스는 정렬했을 때의 인덱스이다.그리고 A 배열을 역순 정렬한다.그러고 나서 A와 B_index 각 값을 곱한 후 더하면 최종 결과가 나온다.이론 상으로는 문제가 없다고 생각했는데 제출 결과 틀렸다고 나왔다.

N = int(input())    # N: 정수 배열의 길이
A = list(map(int, input().split()))
B = list(map(int, input().split()))

B_sort = sorted(B)
B_spare = []
for idx, value in enumerate(B_sort):
    B_spare.append((idx, value))

B_index = []
for i in range(N):
    for j in range(N):
        if B[i] == B_spare[j][1]:
            B_index.append((B[i], B_spare[j][0]))

A.sort(reverse=True)

result = 0
for i in range(N):
    for j in range(N):
        if i == B_index[j][1]:
            result += (A[i] * B_index[j][0])

print(result)

 

위 코드의 문제를 알아냈는데, B 배열에 같은 수가 있을 경우 인덱싱을 잘못 하고 있었다. (같은 인덱스를 여러 번 매김)

visited 배열을 만들어주고 이미 방문한 경우에는 해당 인덱스를 달지 않도록 해주니까 정답으로 매겨졌다.

N = int(input())    # N: 정수 배열의 길이
A = list(map(int, input().split()))
B = list(map(int, input().split()))

B_sort = sorted(B)
B_spare = []
for idx, value in enumerate(B_sort):
    B_spare.append((idx, value))

B_index = []
visited = [0] * N
for i in range(N):
    for j in range(N):
        if B[i] == B_spare[j][1] and not visited[j]:
            B_index.append((B_spare[j][0], B[i]))
            visited[j] = 1

A.sort(reverse=True)

result = 0
for i in range(N):
    for j in range(N):
        if i == B_index[j][0]:
            result += (A[i] * B_index[j][1])

print(result)

 

두 번째. Greedy

정말 Greedy라는 말에 맞게, 직관적으로 풀었다.

B를 재배열하지 말라는 말을 무시하고, A와 B를 모두 정렬했다.

이때 각 값을 곱한 것을 더한 값이 최소가 되어야 하기 때문에 B는 순방향, A는 역방향으로 정렬했다.

너무 간단하게 풀었는데 바로 정답이라고 떠서 조금 허무했다.

N = int(input())    # N: 정수 배열의 길이
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.sort(reverse=True)
B.sort()
result = 0
for i in range(N):
    result += (A[i] * B[i])
print(result)