[삼성 sw 파이썬] 4371 항구에 들어오는 배

[삼성 sw 파이썬] 4371 항구에 들어오는 배

 

문제

항구에 배가 들어오 늘 날을 '즐거운 날' 이라고 하자. 이때 각 배들은 항구를 주기적으로 방문한다. 

예를 들어 주기가 3인 배는 항구에 1일 차 4일 차 7일 차 등에 방문하게 된다.

1일 차부터 기록한 '즐거운 날' 들의 목록이 주어질 때 항구에 들렀던 배의 최소 수를 알아내자.

(이때 모든 배는 1일 차에 방문한다.)

 

입력

첫번째 줄에 테스트 케이스

두 번째 줄부터는 각 케이스의 첫 번째 즐거운 날의 수 n이 주어진다.

각 테스트 케이스의 두 번째 줄부터 n개의 줄에 걸쳐 즐거운 날의 정보가 오름 차순으로 정렬되어 주어진다.

 

출력

각 테스트 케이스마다 항구에 들렸던 배의 최소 수를 출력한다.

 

풀이

각 배들이 들어오는 주기가 존재하면 이때 배의 들어오는 배의 수가 최소가 되는 걸 구하는 문제이다.

즉 수열 문제라 할 수 있다. 여러 주기를 가진 배가 들어오며 이때  그전의 들어왔던 배의 주기와 일치하면 제외하는 형식으로 문제를 풀면 들어오는 배의 최소 수를 구할 수 있다.

나는 각 배들의 주기를 구하고 그 주기가 다른 주기와의 나머지를 계산할 때 0이 나올 경우 같은 주기라 판단하여 제외하는 형식으로 문제를 풀었다.

코드

t=int(input())
for test in range(1,t+1):
    n=int(input())
    array=[]
    ans=[]
    for _ in range(n):
        a=int(input())
        if a!=1:
        #a-1를 넣는 이유는 시작일이 무조건 1 이기 때문이다.
            array.append(a-1)
    
    for i in array:
        if i not in ans:
            check=True
            for j in ans:
                if i%j==0:
                	#이 부분이 같은 주기를 가진거를 확인하는 부분이다.
                    check=False
            if check:
                ans.append(i)
        if len(ans)==0:
            ans.append(i)
    print(f"#{test} {len(ans)}")