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

Thumbnail: Photo by Margarida CSilva (Unsplash)

오늘도 등장한 약수 찾기 문제입니다.

풀이

풀이를 간단하게 정리하면, Counter + 약수 찾기 로 생각할 수 있습니다.

'자신이 쓴 숫자가 다른 사람이 쓴 숫자의 배수이면' 이란 표현은 결국 자신의 약수를 쓴 사람이 몇명 있는지 찾는 것과 같습니다.

Counter?

문제에서 각 사람마다 자신의 약수를 쓴 사람이 몇 명이 있는지 찾아야 합니다. 그렇다면, 각 사람들이 들고 있는 수의 개수를 미리 세어 둔다면 이후 계산 시에 편리할 것입니다. 이를 위해, 입력으로 주어진 사람들의 숫자를 2가지 형태로 저장합니다:

• 입력 순서대로의 정수 배열
• 각 숫자가 몇 개 등장했는지 개수를 센 데이터
  • 각 숫자는 1 이상 100만 이하이므로, 그냥 길이가 100만인 배열을 만들어 저장해도 무방합니다.
  • 등장한 숫자들만 저장하고 싶다면, Map 자료구조를 사용하시면 됩니다. 저는 파이썬의 내장 자료형인 dict를 사용했습니다.

numbers = [0 for _ in range(N)]
exist = {}

for i in range(N):
    n = int(input().strip())
    numbers[i] = n
    try:
        exist[n] += 1
    except KeyError:
        exist[n] = 1

약수 찾기

이제 입력으로 받은 각 숫자에 대해서, 전체 입력에서 자신의 약수가 몇개 존재하는지 찾아내야 합니다. 약수를 계산하는 전형적인 방법으로, 1부터 \(\sqrt{N}\)까지 반복하며 직접 나눠보는 방법을 사용했습니다.

약수를 찾았다면, 기존에 입력 내의 각 숫자의 개수를 세었던 데이터를 토대로 결과값을 계산합니다.

j = 1
while j * j <= x:
    if x % j == 0:
        result += exist.get(j, 0)
        
        if j != numbers[i] // j:
            result += exist.get(numbers[i] // j, 0)
    j += 1 
print(result - 1)   # 자기 자신은 제외한다.

전체 코드

input = open(0).readline
N = int(input())
numbers = [0 for _ in range(N)]
exist = {}

for i in range(N):
    n = int(input().strip())
    numbers[i] = n
    try:
        exist[n] += 1
    except KeyError:
        exist[n] = 1

for i in range(N):
    result = 0
    j = 1
    while j * j <= numbers[i]:
        if numbers[i] % j == 0:
            result += exist.get(j, 0)
            
            if j != (r := numbers[i] // j):
                result += exist.get(r, 0)
        j += 1 
    print(result - 1)   # 자기 자신은 제외한다.