[백준 2953번] 배 (Python)

> 파이썬, 수학, 그리디 알고리즘, 정수론

 

 

 

 

 

📖 문제 : 배 (Python)

 

 

해빈이는 배가 한 척이라도 올까 말까 한 작은 항구 마을에 산다. 그런데 어느 날, 마을을 방문한 적이 있는 모든 배가 한꺼번에 마을을 방문한 날이 있었다. 해빈이는 이 날을 기념해 1일로 센다. 그리고 배가 한 척이라도 마을에 온 날을 신나는 날이라고 하고 특별히 리스트에 기록해두었다.

해빈이는 마을에 방문하는 배들을 관찰한 결과, 이들이 일정한 날자 간격을 두고 주기적으로 항구를 방문한다는 사실을 알아차렸다. 예를 들어, 간격이 3인 배는 1일, 4일, 7일, 10일 등에 해빈이의 마을에 온다.

오늘은 신나는 날이다. 오늘을 포함해서 해빈이의 신나는 날 리스트가 주어질 때, 방문한 배의 최소 수를 구하라. (해빈이는 모든 신나는 날을 리스트에 정확히 적어두었다. 따라서 항상 답이 존재한다.)

 

 

입력

입력의 첫 줄에 정수 신나는 날의 개수 N (2 ≤ N ≤ 5000)이 주어진다.

다음 N줄에는 신나는 날의 번호가 오름차순으로 한 줄에 하나 씩 주어진다. 첫 번째 수와 마지막 수는 각각 해빈이가 관찰을 시작한 날, 그리고 해빈이가 매긴 오늘의 번호이다. 즉, 첫 번째 줄은 항상 1이다. 마지막 수(오늘의 번호)는 10^9보다 작다.

 

 

출력

가능한 배의 최소 수를 출력한다.

 

 

예제 입력 1

3
1
3
4

 

예제 출력 1

2

 

 

 

 

 

 

 

 

내 코드

N = int(input())
List = []
for _ in range(N):
    x = int(input())
    List.append(x)

cnt = 0
List.pop(0)

while True:
    if len(List) == 0:
        break
    temp = List[0] - 1
    for i in range(1, List[-1]+1, temp):
        if i != 1:
            List.remove(i)

    cnt += 1

print(cnt)

 

 

 

Point ! ⭐️ 

• 백준 페이지에 있는 2번째 예제를 보면,

5
1
7
10
13
19

 1 7 10 13 19 라는 의미는 일단 모든 배는 1에서 출발하고, 1 7 10 13 19 만을 지나면서 간격이 같은 배의 최소 갯수를 구하는 문제이다.

여기서는 간격이 6인 배와 9인 배 총 2개로 위의 모든 날이 신나는 날이 될 수 있다. 

간격이 6인 배는,
1 7 13

간격이 9인 배는,
1 10 19 로 

결국 '1부터 시작하여 위에 주어진 날들을 모두 지나쳐야하는 최소 배의 갯수'를 출력하면 되는 것이다. 

이때 규칙을 찾을 수 있는데,
모든 배가 1부터 시작하기 때문에 1과 가장 가까이에 있는 수의 차이가 첫번째 그 차이를 간격으로 둔 배가 존재한다는 것이다.
그 배로 갈 수 있는 수를 모두 pop() 하여

또 1과 가까운 수와 1의 차이가 또 두번째 그 차이를 간격으로 둔 배가 된다는 것이다.

 

이 방법으로 1번 예제를 보면,

3
1
3
4

 

1 3 4 에서 1과 가장 가까운 수 3 -  1 = 2를 간격으로 둔 배 한개 존재.
그러면, 그 배는 1, 3, 5, 7, 이런식으로 가게 되면

남는 수는 

1 4 가 되고, 4 - 1 = 3를 간격으로 둔 배 한 개 존재하여 신나는 날 4도 지나칠 수 있게 되므로

최소 배의 수는 2(간격 2인 배, 간격 3인배) 가 되는 것이다. 

 

 

 

 

 

 

 

백준

https://www.acmicpc.net/problem/2853

2853번: 배