뭔가 맞을 것 같았는데 결국엔 못 풀어서 조금 아쉬운 문제이긴 하다.

17087: 숨바꼭질 6

1. 내 풀이 1: 실패

import sys

N, S = map(int, sys.stdin.readline().strip().split())
D = list(map(int, sys.stdin.readline().strip().split()))
distance = []

for i in D:
    distance.append(abs(S-i))

print(min(distance))

처음에는 수빈이와 동생들 사이의 거리를 뺀 절댓값들 중 가장 작은 것을 찾으면 된다고 생각했다. 하지만...

3번이나 ... 퇴짜 맞고 다시 생각해봤다. 생각해보니까 만약 뺀 거리의 절댓값이

7, 10, 11

이라면? 이러면 결국은 1칸씩 움직여야 하는 것이다. 그래서 내가 구해야 하는 것은 뺀 거리의 절댓값들의 최대공약수 라는 것을 깨달았다...!

2. 내 풀이 2: 실패

import math 
import sys
from itertools import combinations

N, S = map(int, sys.stdin.readline().strip().split())
D = list(map(int, sys.stdin.readline().strip().split()))

distance = []
for i in D:
    distance.append(abs(S-i))

combination = combinations(distance, 2)
GCD = set()
for i in combination:
    GCD.add(math.gcd(i[0], i[1]))

print(min(GCD))

깨달은 대로 구현을 해봤으나,

또 3번이나 퇴짜 맞았다 ^^...

아마 combination을 구하고, GCD에 최대공약수들을 추가하는 과정에서 시간이 많이 소요된 것 같다. 이것 말고도 for문으로 (브루트포스) 구현해봤는데 역시나 시간 초과...

생각해보니 distance 속의 값 중 아무거나 잡고 다른 수와 최대공약수를 구하면 되지 않나 라는 생각이 들었다.

3. 내 풀이 3: 성공

import math 
import sys

N, S = map(int, sys.stdin.readline().strip().split())
D = list(map(int, sys.stdin.readline().strip().split()))

distance = []
for i in D:
    distance.append(abs(S-i))

answer = distance[0]
for i in range(len(distance)):
    answer = math.gcd(distance[i], answer)

print(answer)

또 위에서 얻은 인사이트를 바탕으로 진행해봤다. 그 결과...!

총 7번의 시도 끝에 겨우 맞았다 ^^

다른 풀이도 세 번째 풀이와 굉장히 유사하길래 다른 풀이 소개는 생략하도록 하겠다!

오늘도 신기한 알고리즘의 세계 끝!