[알고리즘][백준] 17087번 숨바꼭질 6 - 파이썬(python) 풀이

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

17087번: 숨바꼭질 6

---

d만큼씩 움직이니까 동생의 위치와 수빈이의 위치 차이를 리스트에 넣어 가장 작은 값을 내면 되지 않을까했는데

import sys

n, s = map(int, sys.stdin.readline().split())

bro = list(map(int, sys.stdin.readline().split()))

num = []

for i in range(n):

    num.append(abs(bro[i] - s))

print(min(num))

틀렸다고 나온다

예제는 차이들이 다 배수로 나오길래...

 

3 5

2 7 3

같은 것이 들어가게 되면 D가 1이 되어야하는데 위의 코드로는 2가 나오게 된다

너무 간단하게 생각하긴 했다

아무튼 동생과 수빈이의 거리 차이의 최대공약수를 찾자

import sys

import math

n, s = map(int, sys.stdin.readline().split())

bro = list(map(int, sys.stdin.readline().split()))

num = []

result = []

for i in range(n):

    num.append(abs(bro[i] - s))

for i in range(n-1):

    for j in range(i+1,n):

        result.append(math.gcd(num[i], num[j]))

print(min(result))

작성하면서도 시간초과날거같은데..? 하더니 시간초과..

 

어느부분에서 줄일수있는건가..!

 

좀 찾아보니

세 수 이상의 최대공약수는 gcd를 반복하는 것으로 구할 수 있는 걸 알게되었다

import sys

n, s = map(int, sys.stdin.readline().split())

bro = list(map(int, sys.stdin.readline().split()))

num = []

def gcd(a, b):

    if b == 0:

        return a

    return gcd(b, a%b)

for i in range(n):

    num.append(abs(bro[i] - s))

result = num[0]

for i in range(1,n):

    result = gcd(result, num[i])    # gcd(a, b, c) = gcd(gcd(a, b), c)

print(result)

 

어느 분은 차이를 set -> list로 중복을 제거하셨는데 그것이 메모리를 더 많이 잡아먹었다...?

import sys

n, s = map(int, sys.stdin.readline().split())

bro = list(map(int, sys.stdin.readline().split()))

def gcd(a, b):

    if b == 0:

        return a

    return gcd(b, a%b)

 

dif = list(set(abs(bro[i] - s) for i in range(n)))  # set로 중복 제거후 다시 리스트화

result = min(dif)

for i in range(len(dif)):

    result = gcd(dif[i], result)

print(result)

17087_숨바꼭질6.py

0.00MB