문제 링크: https://www.acmicpc.net/problem/25710

Thumbnail: Photo by angg Y (Unsplash)

이 문제 덕분에 비둘기집의 원리를 이해했습니다..!

풀이

문제 입력으로 주어지는 배열 a는 최대 100,000개의 원소를 가집니다. 이 배열을 그대로 가지고 점수 계산을 하게 되면, 최대 \((100,000)^2)\번 반복하게 되며 당연하게도 제한 시간을 초과합니다.

하지만, 배열의 원소 \(a_i\)의 범위를 보면 해답을 찾을 수 있습니다. \(1 \le a_i \le 999\)이므로, 사실 100,000개의 원소를 가지는 배열에서는 분명 하나 이상의 수가 중복되어 있을 것입니다. (비둘기집의 원리!)

💡 비둘기 집의 원리란?
간단히 설명하면, \(N+1\)마리의 비둘기를 \(N\)개의 상자에 넣게 되면 적어도 한 상자에는 두 마리 이상의 비둘기가 들어있다는 원리입니다.

'입력의 범위보다 출력의 범위가 작아 다른 입력값이어도 동일한 출력값이 나올 수밖에 없는 상황'을 설명하는데 사용됩니다.

따라서, 입력으로 주어진 배열 내에 중복을 제거한 배열을 만들면, 훨씬 더 적게 반복해도 정답을 구할 수 있습니다. 중복을 제거할 때, 입력에서 여러 번 등장한 수는 2개까지만 배열에 넣고 이후로는 제거합니다. (자기 자신과의 곱은 가능하기 때문입니다.)

전체 코드

from sys import stdin

N = int(stdin.readline())
numbers = [0 for _ in range(1001)]  # 1~999까지의 수만 입력값 내에 존재하므로, 그 개 수를 세자.
calc_array = []

for number in map(int, stdin.readline().split()):
    numbers[number] += 1
    if numbers[number] <= 2:
        calc_array.append(number)   # 어짜피 2개 이상으로 중복되어도 2개만 포함된거랑 경우의 수는 같다 (자기 자신과의 곱, 자기 자신과 다른 수와의 곱)

res = 0
for i in range(0, len(calc_array)):
    for j in range(i+1, len(calc_array)):
        x = calc_array[i] * calc_array[j]
        r = 0
        while x > 0:
            r += x % 10
            x //= 10
        if r > res:
            res = r
print(res)