단계적으로 풀기에서 그리디 알고리즘 파트의 문제인 "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)이 된다. 그리고 이후도 마찬가지로 예측해 볼 수 있다. 그리고 이를 모두 더하면 우리가 원하는 결과 값이 나오게 된다.
식으로 나타내보면 다음과 같다.
n∑k=1k(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보다 크고 109보다 작거나 같음)들을 모두 M 으로 나누었을 때 나머지가 같게 되는 M을 전부 구하면 된다. 여기서 M은 항상 존재한다고 한다.
주어진 N개의 자연수는 다음과 같이 표현할 수 있을 것이다.
a1M1+r1, a2M1+r1, a3M1+r1, ... ,anM1+r1. 그리고 M은 여러 개 존재할 수 있기 때문에 다음과 같이 표현될 수도 있다. (둘 다 같은 자연수들로 이뤄져 있다. 표현 방식만 다른 것일 뿐)
b1M2+r2, b2M2+r2, b3M2+r2, ... ,bnM2+r2.
여기서 a1이 a1~an 중 가장 작고, b1이 b1에서 bn중 가장 작다고 가정해 보자. (aiM1+r1 = biM2+r2) 그럼 이 a1M1+r1, b1M2+r2도 가장 작은 수가 된다. 이 수와 나머지 자연수들과의 차를 구하면, r1과 r2를 제거한 결과를 얻을 수 있다.
(a2−a1)M1, (a3−a1)M1, (a4−a1)M1, ... ,(an−a1)M1.
(b2−b1)M2, (b3−b1)M2, (b4−b1)M2, ... ,(bn−b1)M2.
여기서도 ((ak−ai)M1 = (bk−bi)M2가 성립한다.)
우리가 원하는 결과는 M1,M2,M3...Mi이다. 이를 구하려면 위의 (자연수-최소값) 으로 구성된 수들의 최대 공약수를 구한 후, 이 최대 공약수의 약수(또는 인수)를 구하면 된다.
코드는 다음과 같으며, 역시 파이썬으로 작성하였다.
#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 = ' ')
'study_life' 카테고리의 다른 글
오픽 첫 시험 후기 (0) | 2020.08.29 |
---|---|
[논문 리뷰] 자연어 처리(이해), 이대로 옳은가? - ACL2020 Best theme paper (0) | 2020.08.11 |
[선형대수] 대각 행렬 (0) | 2020.06.13 |
[블로그] 카카오 AdFit(애드핏) 최근 콘텐츠가 부족합니다. (0) | 2020.06.11 |
[선형대수] A의 역행렬이 존재하지 않을 때, AB와 BA의 역행렬이 존재하지 않음을 보이시오. (2) | 2020.05.03 |
댓글