[실버 1] 2853번: 배

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

2853번: 배

---

문제

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

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

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

입력

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

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

출력

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

---

사고의 흐름

• 에라토스테네스의 체를 이용한 문제 같은데? N을 상한으로 잡고 N보다 작은 소수들에 해당하는 간격만큼 떨어진 숫자들을 신나는 날 리스트에서 지우면서 카운트를 세면 되겠다.
• 리스트 안의 숫자를 소수로 나눈 다음 나머지가 1이면 지우면 될 듯?
• 배의 수가 최소가 되어야 하므로 작은 소수부터 고려하기 시작하면 그 소수의 배수의 간격을 지닌 배가 있다 하더라도 상관은 없다. 어차피 간격이 3인 배 한 척이나 6인 배 한 척이나 카운트는 똑같이 1만 올라갈 테니까, 그 둘을 구분할 필요는 없다.
• 근데...이렇게 푸는 게 과연 '그리디'스러운 걸까?
• "어차피 간격이 3인 배 한 척이나 6인 배 한 척이나 카운트는 똑같이 1만 올라갈 테니까, 그 둘을 구분할 필요는 없다." 이 부분이 그리디 알고리즘에 부합한다고 할 수 있지 않을까? 더 작은 소수를 선택하는 것(최적의 선택)만으로 부가적인 케이스를 커버할 수 있으니까.
• 에라토스테네스의 체를 사용할 때는 상한을 N이 아니라 N의 제곱근으로 잡아도 된다. 예전에 습득했던 지식인데 왜 그런지는 잘 모르겠다. 이와 관련해서 공부해봐야겠다.
• 굳이 에라토스테네스의 체를 구현해서 소수를 찾아야 하나? 파이썬 math 라이브러리에 있을 법도 한데...한번 찾아보자.
• 그런 건 없네... 그렇다면 에라토스테네스의 체를 구현하기보다 그냥 제곱근 N까지 모든 수를 테스트해봐야겠다. 차라리 그게 반복문을 덜 쓰니까 실행 시간을 단축할 수 있을 거다.

 

• 소스코드를 제출했는데 시간 초과가 떠서 언어를 Pypy3로 바꿔봤지만, 여전히 시간 초과가 떴다. 이중 반복문을 쓰면 안 되겠다.
• 리스트 안의 원소를 반복문을 사용해서 하나하나 인덱싱해서 지웠는데, 이게 시간 복잡도를 올릴 뿐더러 파이썬스럽지도 않다. 다른 방법을 찾아보자.
• 리스트 컴프리헨션을 쓰면 되겠다. 정말 강력한 기능인데?

 

• 처음 생각한 문제풀이 방식이 틀렸다. 만약 입력이 1, 4, 7 이 있으면 배의 수는 당연히 간격이 3인 배 1척이 전부겠지만, 내가 만든 알고리즘대로라면 간격이 2인 배와 3인 배 총 2척이 나온다. 다시 생각해보자. 시간이 많이 지나서 포기.

남이 작성한 소스코드

mnkycoder 님:
https://velog.io/@jychan99/%EB%B0%B1%EC%A4%80BOJ-2853.-%EB%B0%B0-Silver-2

피드백

• 모든 소수를 이용해 간격을 파악할 필요가 없다. 어차피 간격이 좁은 배들부터 차례로 정렬되어 Input이 들어오기 때문이다. 즉, 첫 번째 원소와 두 번째 원소 사이의 간격을 이용해 해당 간격의 배들을 모두 지우고, 이를 반복하면 된다.
• 문제를 브론즈부터 풀자. 마음만 앞서나가지 말고 내 수준에 맞는 문제들을 골라 차근차근 풀어보자. 못해도 1~2시간 내에 답을 떠올릴 수 있어야 한다.