ps:problems:boj:1424
새 앨범
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 1424 |
문제명 | 새 앨범 |
레벨 | 골드 2 |
분류 |
애드혹 |
시간복잡도 | O(1) |
사용한 언어 | Python 3.11 |
제출기록 | 30616KB / 40ms |
최고기록 | 40ms |
해결날짜 | 2022/12/18 |
풀이
- 단순하게 수식으로 나오긴 하는데, 꼼꼼하게 체크하지 않으면 실수할 여지가 좀 있다.
- 다행인점은 주어진 테케가 타이트한 편이라서 실수 파악하기가 쉬운 편이긴 하다.
- 한 CD에 들어갈수 있는 노래의 최대 갯수 K를 구하자. K*L+(K-1)≤C 여야 하므로, K=floor((C+1)/(L+1)) 이다.
- 이제 CD들을 전부 K곡으로 채우고, 남는 노래들로 CD 하나를 만들면 되지 않을까? 근데 K가 13의 배수이면 안되니까 그럴 경우에는 K-=1을 해주자.
- 그래도 안되는 경우가 있다. K보다 실제 노래 갯수 N이 작으면 K와 관계 없이 N개가 수록될텐데, 이때 N이 13의 배수이면 문제가 된다. K= min(K, N) 을 추가해주자
- 이렇게 K를 정확히 구했는데도 아직도 추가로 처리해야 하는 경우가 있다. K곡씩 수록된 CD들을 만들고, 남은 노래들 N%K개로 CD를 마지막 CD를 하나 더 만들건데, N%K가 13의 배수가 되는 경우이다.
- K곡씩 수록된 CD에서 한곡을 빼서 K-1곡만 넣고, 마지막 CD에 N%K+1 곡을 넣으면 CD 장수를 추가하지 않고 수록이 가능하다. 하지만, K-1이 13의 배수인 경우에는?? 그러면 K-2곡을 넣고 마지막에 N%K+2곡을 넣으면 해결되지 않을까? 그런데, N%K+2곡을 넣을때 시간이 초과되는 경우에는 이 방법이 안된다. 이 경우에는 할수없이 CD를 한장 더 추가해서 K, N%K-1, 1 이런식으로 CD들을 구성해야 할것이다.
- 자 그럼 정리하자. 예외 케이스를 제외하고는 ceil(N/K)장의 CD로 수록이 가능하다. 예외케이스는 (N%K)가 0이 아닌 13의 배수이면서 K==N%K+1인 경우이고 이때는 ceil(N/K)+1 장의 CD가 필요하다
코드
"""Solution code for "BOJ 1424. 새 앨범".
- Problem link: https://www.acmicpc.net/problem/1424
- Solution link: http://www.teferi.net/ps/problems/boj/1424
"""
def main():
N = int(input())
L = int(input())
C = int(input())
song_count_per_cd = (C + 1) // (L + 1)
song_count_per_cd = min(song_count_per_cd, N)
if song_count_per_cd % 13 == 0:
song_count_per_cd -= 1
q, r = divmod(N, song_count_per_cd)
if r == 0:
answer = q
elif r % 13 == 0 and song_count_per_cd == r + 1:
answer = q + 2
else:
answer = q + 1
print(answer)
if __name__ == '__main__':
main()
ps/problems/boj/1424.txt · 마지막으로 수정됨: 2022/12/18 11:23 저자 teferi
토론