🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]2981번 - 검문

2981번 - 검문

문제

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

예제 입력 1

예제 출력 1

2 4

예제 입력 2

예제 출력 2

해결할 방법을 생각해보자.💡

상당히 난이도가 있는 문제라서 구글에서 다른 풀이들을 많이 보고 풀었다. 예제와 같이 세개의 수 6, 34, 38이 주어졌을 경우에 생각해보자. 이 세 수의 M은 2와 4가 될 수 있다고 한다. 따라서

= ? + 2
= ? + 2
= ? + 2

이런 형식이 된다. 공통된 나머지를 제외할 경우에는 4, 32, 36 이렇게 되는데 이 수들은 공통된 수로 곱해진것이므로

= 1 x 4
= 8 x 4
= 9 x 4

이렇게 되었다고 볼 수 있다. 그러면 다시 종이에 적은 세가지 수를 이렇게 표현할 수 있다.

= 1 X 4 + 2
= 8 X 4 + 2
= 9 X 4 + 2

그렇다면 이 경우를 숫자가 아닌 식으로 표현하면 이렇게 표현할 수 있다.

A = (a * M) + n
B = (b * M) + n
C = (c * M) + n

여기서 + 되고있는 n을 제거하려면 B-A나 C-B같은 형태로 연산을 해줘야한다. 그러면 이런 결과가 나올 것이다.

B - A = (b-a) * M
C - B = (c-b) * M

이렇게 수를 뺄셈해준 것들은 M의 배수라는 것을 알 수 있다. 그러면 이것들의 최대공약수가 M이 될 수 있다. 그리고 나머지 M들은 최대공약수의 약수가 된다. 문제에 나와있는 예제 2번으로 이 설명을 다시 생각해보자. 예제 2번에서는 5, 17, 23, 14, 83 이렇게 5개의 수를 입력받고 있다. 그러면 이 수들을 순서대로 빼기를 해주자.

- 17 = -12
- 23 = -6
- 14 = 9
- 83  = -69

뺄셈을 해준 것들을 절대값만으로 생각해서 최대공약수를 구해보면, 최대공약수가 3이 나온다. 3은 1과 자기 자신을 제외하고는 없기때문에 출력이 3 하나만 나오게된다.

이제 코드로 문제를 해결해보자. 우선 라이브러리 두개를 호출해주자, gcd() 메소드를 사용하기 위한 math라이브러리와 입력속도를 줄이기 위한 sys라이브러리를 호출하자.

import sys
import math

그리고 수의 개수 N을 받아주고 nums라는 리스트를 만들어서 수들을 append해주자.

N = int(sys.stdin.readline())
nums = []
for i in range(N):
    nums.append(int(sys.stdin.readline()))

이제 나누었을 때 똑같은 나머지를 제거하기 위한 작업을 해줘야한다. 리스트에 있는 각 수들을 뺄셈한 값을 구해주자. M이라는 빈 리스트를 만들어 반복문의 인덱스를 사용해 뺄셈을 하고 그 절대값만 M에 append해주자. 반복문의 범위는 수가 3개일 경우 2번만 반복하면 되므로, 리스트 길이에서 -1 한 범위 까지 반복되게 만들자. 그리고 최대공약수 비교를 위해 리스트를 오름차순으로 정렬해주자.

M = []
for i in range(len(nums)-1):
    M.append(abs(nums[i] - nums[i+1]))
M.sort()

이제 이러면 가장 작은 값이 [0]에 위치하게 되었을 것이다. 이것을 gcd라는 변수에 저장해주자. 그리고 M[0]을 제외하고 인덱스를 사용해 gcd함수를 사용해 최대공약수를 구하며 최대공약수를 갱신해준다.

gcd = M[0]
for i in range(1, len(M)-1):
    gcd = math.gcd(gcd, M[i])

이러면 최대공약수는 구해진 셈으로 해당 최대공약수의 약수만 구하면 된다. 결과라는 의미의 result 리스트를 만들어주고 반복문을 사용해 gcd의 약수들을 구해줄 것이다. 그런데 이 수의 범위는 1 <= 수 <=1,000,000,000 이렇다. 따라서 이 큰 수를 반복한다면 시간초과에 걸릴 수 밖에 없다. 하지만 시간을 줄이는 방법이 있다. 18이라는 수를 2로 나누었을 경우에는 나머지가 0이되어 2가 약수가 될 수 있다. 하지만 그 나눈 수 2 말고도, 나눈 몫 9도 약수가 된다. 이 점을 이용하면 연산을 반으로 줄일 수 있다. math.sqrt(gcd)로 최대공약수의 제곱근을 구해주고 정수형으로 바꿔준 후 1을 더한 범위까지 반복문을 실행하면 시간초과를 면할 수 있다. 약수들을 구해준 뒤에 자기 자신도 append 해주는 것도 까먹지 말자.

for i in range(2, int(math.sqrt(gcd)) + 1):
    if gcd % i == 0:
        result.append(i)
        result.append(gcd // i)
result.append(gcd)

이렇게 구하고 나서 중복되는 값들을 set를 사용해 제거해준 뒤에 sorted()로 정렬해주고 출력의 끝을 공백으로 두고 출력해주면 끝이다!

for i in sorted(set(result)):
    print(i, end = " ")

코드 💻

import sys
import math

N = int(sys.stdin.readline())
nums = []
for i in range(N):
    nums.append(int(sys.stdin.readline()))

M = []
for i in range(len(nums)-1):
    M.append(abs(nums[i] - nums[i+1]))
M.sort()

gcd = M[0]
for i in range(1, len(M)-1):
    gcd = math.gcd(gcd, M[i])

result = []

for i in range(2, int(math.sqrt(gcd)) + 1):
    if gcd % i == 0:
        result.append(i)
        result.append(gcd // i)
result.append(gcd)

for i in sorted(set(result)):
    print(i, end = " ")

해결 로그

문제 푼 날짜	체크
2022-08-01	✔

2022 196
2021 22

맨 위로 이동 ↑