백준문제풀이-검문&정수론공부

일단 문제풀이와 정답률을 봤다 문제 제출한사람중에 시간초과한 사람들이 굉장히 많았다 

보통 이럴경우는 창의력을 발휘해서  시간복잡도를 낮추던가 아니면 수학적으로 접근하여 시간복잡도를 낮추는 경우가 대부분이다

결론부터 말하자면 후자였다

 

처음엔 문제 자체도 제대로 이해못하고 풀었다 나누는값이 작은수보다 크면 안된다고 생각했다

import sys
input=sys.stdin.readline
# 입력받기
숫자들=[int(input()) for i in range(int(input()))]
# 나머지로 나올수있는값은 가장 1~가장작은수의 값으로 한정되어있다
for i in range(2,min(숫자들)+1):
    count=0
    for j in range(len(숫자들)-1):
        if 숫자들[j]%i != 숫자들[j+1]%i:
            count+=1
            break
    if count == 0:
        print(i, end=' ')

 

두번째로 꺠달은것은 나누는수는 두번째로 작은수-가장작은수보다 클수없다는 사실이었다

import sys
input=sys.stdin.readline
# 입력받기
숫자들=[int(input()) for i in range(int(input()))]
# M의 범위:2 ~ 두번째로 작은수-가장작은수

# 사본만들기
a=숫자들.copy()
# 중첩제거
b=list(set(숫자들))
# 정렬
b.sort()
# 범위 나타내기
for i in range(2,b[1]+1):
    count=0
    for j in range(len(a)-1):
        if a[j]%i==a[j+1]%i:
            pass
        else:
            count+=1
            break
    if count==0:
        print(i, end=' ')

범위를 지정한후 브루트포스형식으로 도전 하지만 시간초과가 났다 백준에서 for문 두개 겹치는행동은 죄악이다

 

세번째로 깨달은것은 각요소끼리 차이가 가장 적은것을 골라서 그수의 공약수를 구하면 답이나온다는사실이었다

import sys
input=sys.stdin.readline
# 각요소끼리 차이가 가장 적은것을 골라서 그수의 공약수를 구하면 그게 답이다
# 소트한담에 바로 앞요소끼리뺴기
# 입력받기
chai=[]
ans=[]
숫자들=[int(input()) for i in range(int(input()))]
숫자들.sort()
for i in range(len(숫자들)-1):
    chai.append(숫자들[i+1]-숫자들[i])
b=min(chai)
for i in range(1,int(b**0.5//1)+1):
    if b%i==0:
        ans.append(i)
        ans.append(b//i)
ans.remove(1)
ans=list(set(ans))
ans.sort()
for i in ans:
    print(i, end=' ')

하지만 뜨는 결과는 틀렸습니다 도대체 왜! '이게웨안되'를 외치며 망연자실 답답한마음에 계속 질문방에서 반례를 찾아보지만 도움되는건 없었다 스스로 곧 반례를 찾게되는데 그것은 4 6 12 18 22 였을것이다

이 반례로 나는 왜 내가 틀렸는지 알게되었다

 

사실 오류의원인을 아는건 사실 굉장히 행복한일이다 왜 오류가 나는지 모를때는 복합적인 생각이든다

 

네번째로 깨달은것은 요소간 가장 차이가 작은값과, 가장작은값과 그다음으로 작은값의 차의 공약수가 바로 정답이라는 사실이었다

import sys
input=sys.stdin.readline
# 각요소끼리 차이가 가장 적은것을 골라서 그수의 공약수를 구하면 그게 답이다
# 소트한담에 바로 앞요소끼리뺴기

# 소트후 요소간 차이가 가장작은값 구하기
chai=[]

숫자들=[int(input()) for i in range(int(input()))]
숫자들.sort()
for i in range(len(숫자들)-1):
    chai.append(숫자들[i+1]-숫자들[i])
b=min(chai)
# print(len(chai))

# 가장작은수와 그다음으로 작은수의 차
a=숫자들[1]-숫자들[0]

# a와 b의 최대공약수 구하기
ans=[]
for i in range(min([a,b]),int(min([a,b])**0.5//1)-1,-1):
    if a%i==0 and b%i==0:
        최대공약수=i
        break
for i in range(1, int(최대공약수**0.5//1)+1):
    if 최대공약수%i==0:
        ans.append(i)
        ans.append(최대공약수//i)

ans.remove(1)
ans=list(set(ans))
ans.sort()
for i in ans:
    print(i, end=' ')

드디어 맞았고 나는 편하게 잠을 잘수있게 되었다 

알고보니 이문제는 유클리드 알고리즘으로 푸는 문제라는것을 후에 알게되었고

이어질 포스팅은 나의 유클리드 알고리즘 공부 내용이다