[D3] 4371. 항구에 들어오는 배 (Python 파이썬 풀이)

문제 : 4371. 항구에 들어오는 배

문제

민석이는 항구가 있는 작은 마을에 산다.

이 항구에는 배가 아주 드물게 지나다닌다.

민석이는 어느날 모든 배들이 항구에 들어온 것을 보았다.

민석이는 이 날을 1일차로 지정하였다.

민석이는 배가 한 척이라도 항구에 들렀던 날을 “즐거운 날"로 이름짓고, 1일차부터 즐거운 날들을 모두 기록하였다.

그러던 중, 한 가지 규칙을 발견했는데, 그 규칙은 각 배들은 항구에 주기적으로 들른다는 것이었다.

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

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

이 때, 항상 답이 존재하는 입력만 주어진다.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에 즐거운 날의 수 N이 주어진다. (2 ≤ N ≤ 5000)

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

시작하는 날은 항상 1일이고, 마지막 날은 109보다 작은 값이다.

출력

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

예제 입력	예제 출력
3 // Test Case 수 3 // Test Case 1, N =3 1 // N줄에 걸쳐 즐거운 날의 정보 입력 3 4 5 1 7 10 13 19 3 1 500000000 999999999	#1 2 // Test Case 1의 정답 #2 2 #3 1

문제 해석

문제를 읽어보면, 민석이는 항구에 배가 한 척이라도 있을 때마다 입력값에 기록을 하고 있다. N회 걸쳐서 기록을 하였고, 배들은 일정한 간격으로 왕복을 하고 있을 때, 가질 수 있는 왕복하고 있는 배의 개수를 찾으면 되는 것이다. 그리고 모든 배는 1일차에 들어와 정박해 있다.
첫번째 입력값을 보면 3회에 걸쳐서 1일차, 3일차, 4일차에 배가 있다. 그러면 첫번째 배는 1일차에 정박하고 3일차에 정박했다는 것을 알 수 있고, 이 배는 다음에 5일차에 정박할테니, 4일차에 들어온 배는 다른 배라는 것을 알 수 있다. 이를 쉽게 계산하기 위해서 모든 일 수에 1씩 빼보자. 그러면
0일, 2일, 3일의 입력값이 있다. 그러면 한 배는 2일마다, 다른 배는 3일마다 들어온다는 것을 쉽게 알 수 있다.

이 풀이가 맞는지 두번째 입력값을 보자. N은 5이고, 1,7,10,13,19일마다 배가 있다. 이번에도 1씩 모두 빼면 [0일,6일,9일,12일,18일]이라는 것을 알 수 있다. 가장 빈번하게 들어오는 배는 6일마다 들어오고 있으니 6의 배수인 값들을 빼면 9일에 들어온 배만 남는다. 그러므로 최소가 되는 배의 개수는 2척이다.

세번째도 봐보자. N은 3이고, 일수에 1일씩 빼서 보면 0일, 499999999일, 999999998일이다. 가장 빈번하게 들어온 배는 499999999일 후에 들어왔고 이 배가 다음에 들어오는 날은 499999999일X2 인 999999998일 이다. 즉, 한 배만 존재한다. (이 배는 1,369,863년마다 한 번씩 들어온다.)

이제 이를 파이썬으로 나타내 보자.

풀이

주석으로 옆에 달아뒀으나, 이해안되면 언제든지 댓글로 달아주세요.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

for Count in range(int(input())): # T회 실행     List = []     for _ in range(int(input())): # N회 실행, 코드를 줄이기 위해서 range안에 input()값을 바로 집어넣음         List.append(int(input())-1) # N회 동안 (입력값-1)을 List 안에 집어넣는다.     Answer = 0 # 정답이 될 배의 최소 수     while any(List): # List값을 모두 0으로 될때까지 while을 돌린다.         for i in range(1,len(List)): # 첫번째 값은 어차피 0이니 두번째 값부터 확인한다.             if List[i]: # 만약 값이 0이 아니라면                 Answer += 1 # Answer 값을 1씩 올린다.                 A = List[i]                  for j in range(i,len(List)): # i번째 값부터 끝까지 확인해서 A의 배수인 값들을 확인한다.                     if not List[j]%A: # 나머지 값이 0이면                          List[j] = 0 # 그 값은 0이라고 한다     print("#{} {}".format(Count+1,Answer)) # 출력값과 동일한 형식으로 출력한다.

cs

출처

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWMedCxalW8DFAXd&categoryId=AWMedCxalW8DFAXd&categoryType=CODE