[알고리즘] 백준. ATM #11399, 검문 #2981

 

단계적으로 풀기에서 그리디 알고리즘 파트의 문제인 "ATM"과 수학3 파트 문제인 "검문"을 풀어보았다. 

 

ATM

 

예를 들어 다음과 같이 사람들이 ATM 앞에서 업무를 처리하기 위해 줄을 섰다고 하자. 그리고 밑의 숫자는 각 사람들이 업무를 보는 데 걸리는 시간이다. 

 

각 사람들이 자신의 업무를 마치는 데까지 걸리는 시간은 다음과 같다. 

 

이를 단순화 시켜보면, "기다리는 시간+자신의 업무 시간"만큼의 시간이 걸린다. 문제에서 요구하는 것은 모든 사람이 자신의 업무를 마치는 데 걸리는 시간을 최소화 시키도록 사람들을 줄 세우고 싶은 것이고, 그렇게 줄을 섰을 때 마지막 사람이 자신의 업무를 마칠 때까지 걸린 시간을 구하고자 하는 것이다. 

 

위에서 "기다리는 시간+자신의 업무 시간"을 살펴보면, 결국 우리가 줄일 수 있는 부분은 "기다리는 시간"이다. 이 시간은 곧 자신의 앞 사람의 업무 시간이다. 따라서 기다리는 시간을 최소화 한다는 것은 자신 앞에 업무 시간이 짧은 시간인 사람이 오는 것이며, 맨 앞 자리는 모든 사람 보다 앞에 있으며 모든 사람보다 업무 시간이 짧아야 하니, 가장 짧은 업무시간을 가진 사람이 와야 한다. 그리고 그 다음에는 맨 앞 사람을 제외한 나머지 사람들 중에서 업무 시간이 가장 짧은 사람이 오는 식으로 줄을 서면 된다. 즉, 오름차순으로 정렬되면 된다! 이를 정렬하면 다음과 같은 결과를 예상해 볼 수 있다.

 

 

이제 중요한 건 최소 시간을 계산하는 것인데, 정렬을 따로 해준 후 배열을 돌면서 1 + (1+2) + (1+2+3) +... 이런 식으로 계산해도 되지만, 조금만 더 생각해보면 더 쉽게 계산할 수 있다. 맨 앞사람은 자신의 업무 시간(1)이 걸리며 자신의 뒷사람들 모두에게 자신의 업무 시간만큼 기다리게 한다. 즉, n명이 있으면, 1*(1+(n-1)) = 1*n, 2번째 사람은 자신의 업무 시간(2)만큼 시간이 걸리고 뒷사람 모두에게 자신의 업무 시간만큼 기다리게 하니, 2*(1+(n-2)) = 2*(n-1)이 된다. 그리고 이후도 마찬가지로 예측해 볼 수 있다. 그리고 이를 모두 더하면 우리가 원하는 결과 값이 나오게 된다. 

식으로 나타내보면 다음과 같다. 

$$\sum_{k=1}^{n} k(n-k+1)$$

이를 풀어서 더 단순하게 만들 수도 있겠지만, 이 정도 선에서 코드로 옮기고자 한다. 코드는 파이썬으로 작성하였다.

 

#ATM 11399

#입력값 받기
n = int(input())
ls = list(map(int, input().split()))

ls = []
res = 0

#loop돌면서 최솟값(K)에 대하여 k * (n-k+1)을 결과 값에 더해준다. 
#정렬을 쓰지 않고 전체 리스트에서 최솟값을 찾고 그 최솟값으로 계산을 한 후 
#해당 최솟값을 리스트에서 제거하는 방식으로 진행하였다.
for i in range(n, 0, -1):
    min_n = min(ls)
    res += min_n*i
    ls.remove(min_n)
    
print(res)

 

 

검문

 

검문 문제는 수학3 파트에 있는 문제로, 수학3 파트는 정수론, 조합론에 관한 문제들인데 이런 식으로 접근하는 게 맞는지는 잘 모르겠다.. (사실 위 문제도 그리디 알고리즘을 제대로 적용한 지는...)

 

문제는 다음과 같다. 

N개의 자연수(N은 2이상, 100이하)가 주어진다. 이 자연수(1보다 크고 $10^9$보다 작거나 같음)들을 모두 M 으로 나누었을 때 나머지가 같게 되는 M을 전부 구하면 된다. 여기서 M은 항상 존재한다고 한다.

 

주어진 N개의 자연수는 다음과 같이 표현할 수 있을 것이다. 

$a_1M_1+r_1$, $a_2M_1+r_1$, $a_3M_1+r_1$, ... ,$a_nM_1+r_1$. 그리고 M은 여러 개 존재할 수 있기 때문에 다음과 같이 표현될 수도 있다. (둘 다 같은 자연수들로 이뤄져 있다. 표현 방식만 다른 것일 뿐)

$b_1M_2+r_2$, $b_2M_2+r_2$, $b_3M_2+r_2$, ... ,$b_nM_2+r_2$. 

여기서 $a_1$이 $a_1$~$a_n$ 중 가장 작고, $b_1$이 $b_1$에서 $b_n$중 가장 작다고 가정해 보자. ($a_iM_1+r_1$ = $b_iM_2+r_2$) 그럼 이 $a_1M_1+r_1$, $b_1M_2+r_2$도 가장 작은 수가 된다. 이 수와 나머지 자연수들과의 차를 구하면, $r_1$과 $r_2$를 제거한 결과를 얻을 수 있다. 

 

$(a_2-a_1)M_1$, $(a_3-a_1)M_1$, $(a_4-a_1)M_1$, ... ,$(a_n-a_1)M_1$.

$(b_2-b_1)M_2$, $(b_3-b_1)M_2$, $(b_4-b_1)M_2$, ... ,$(b_n-b_1)M_2$.

여기서도 ($(a_k-a_i)M_1$ = $(b_k-b_i)M_2$가 성립한다.)

우리가 원하는 결과는 $M_1, M_2, M_3 ... M_i$이다. 이를 구하려면 위의 (자연수-최소값) 으로 구성된 수들의 최대 공약수를 구한 후, 이 최대 공약수의 약수(또는 인수)를 구하면 된다.

 

코드는 다음과 같으며, 역시 파이썬으로 작성하였다.

#2981

#최대 공약수 구하는 함수
def gcd(a, b): 
    while b:
        a, b = b, a%b
    return a

n = int(input())
ls = []

for i in range(n):
    ls.append(int(input()))
min_n = min(ls) #최솟값 구하기

for i in range(len(ls)):
    if ls[i] > min_n:
        ls[i] = ls[i] - min_n #모든 자연수를 최솟값으로 빼주기
ls.remove(min_n) #최솟값은 원래 리스트에서 제거

#위에서 계산한 자연수-최솟값들 모두의 최대 공약수 구하기
gcd_n = ls[0] 
for i in range(len(ls)):
    gcd_n = gcd(gcd_n, ls[i])

#최대 공약수의 약수 구하기
for i in range(2, gcd_n+1):
    if gcd_n%i==0:
        print(i,end = ' ')