사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
U J L K F
 
ps/problems/boj/1424.txt · 마지막으로 수정됨: 2022/12/18 11:23 저자 teferi