BOJ 백준 1026: 보물

Table of contents

들어가며

이 문제는 그리디 알고리즘 문제입니다.
브루트 포스를 하려고 하면 50!이라는 엄청나게 많은 가지수가 나와서, 그렇게 풀지 못합니다. 하기 노트는 제가 풀면서 한 노트 필기와 풀고 나서 사고 과정을 조금 정제한 노트 필기를 합한 것입니다.

풀이 과정

결국 A 배열은 B의 계수로 볼 수 있습니다.
그래서 B배열의 원소들은 재배열 제약으로부터 자유로워지고, 그냥 A와 B 각각 내림차순, 오름차순으로 정렬해서, 각 원소를 곱한 값을 구하면 됩니다.

AC 받은 Python 코드

import sys

input = sys.stdin.readline
MAX_LEN = 50
MAX_VAL = 100


def get_S():
    ret = 0
    for i in range(N):
        ret += A[i] * B[i]
    return ret


if __name__ == "__main__":
    N = int(input().rstrip())
    A = [*map(int, input().rstrip().split())]
    B = [*map(int, input().rstrip().split())]
    # print("A: ", A)
    # print("B: ", B)
    # A가 B의 계수라고 생각하면 된다
    A.sort(key=lambda x: -x)
    B.sort()
    print(get_S())