[swea] 4371번: 항구에 들어오는 배 - 파이썬(python)

모든 배는 1일에 들어온다.

즐거운날은 오름차순으로 정렬이 되어있으므로, 2번째 날짜부터 마지막 날짜까지 탐색하면서 주기를 계산한다.

계산한 주기마다 해당되는 날짜가 ship 집합에 들어있지 않다면 ship 이라는 집합에 추가하고,

배의 개수를 1 증가한다.

 

ex)

즐거운 날 :1 4 6 7 9 10 11 13 16 17 19

첫번째 주기 : 4-1 = 3

ship -> 4,7,10,13,16,19

두번째 주기 : 6-1 = 5

ship -> 4,6,7,10,11,13,16,19

세번째 주기 : 7-1 = 6 -> 이미 ship 에 들어있으므로, 해당 주기의 약수값을 가지는 주기가 이미 존재하는 것이다. 따라서 패스

세번째 주기 : 9-1 = 8 

ship -> 4,6,7,9,10,11,13,16,17,19

 

10일부터 19일까지는 이미 ship 에 들어있으므로 패스.

 

따라서 최소 배의 개수는 3이다.

나의 풀이

T = int(input())
answer = []
for t in range(1, T+1):
    n = int(input())
    day = []
    for _ in range(n):
        day.append(int(input()))
    ship = set()
    cnt = 0
    for i in range(1, len(day)):
        if day[i] in ship:
            continue
        gap = day[i] - 1
        for j in range(1+gap, day[-1]+1, gap):
            ship.add(j)
        cnt += 1

    answer.append(f'#{t} {cnt}')
print(*answer, sep='\n')