새 앨범 ( 1424 번 )

1424번: 새 앨범

 

---

🧠 알고리즘

• 그리디(탐욕적) 기반 시뮬레이션
• 음반에 담을 수 있는 최대 곡 수를 계산하고, 제약 조건(13의 배수 금지)을 적용하며 반복적으로 음반을 채움

 

✔️ 동작 방식

• 최대 수록 곡 수 계산 >> 공식: count(L + 1) <= (C + 1) 에서 도출 → (C + 1) // (L + 1)
• 반복 처리 >> 단, 마지막 남은 곡이 13의 배수일 경우 → 현재 음반에서 한 곡 빼고 조정
• 음반 카운트 증가 & 곡 수 차감
• 정답 출력

---

 

🧾 코드

import sys

# 13으로 나누어 떨어질경우 -1 뺴기
def _na_13_check(number):
    return number if (number % 13) != 0 else number - 1
    
def _main(N, L, C):
    answer = 0
    """
        저장 할수 있는 노래 최댓값
        count * L + count - 1 <= C
        count * L + count <= (C + 1)
        count(L + 1) <= (C + 1)
        즉, count <= (C + 1) // (L + 1)
    """
    max_count = (C + 1) // (L + 1)
    max_count = _na_13_check(max_count)

    # 모든 노래 수록 할 떄 까지 계속 진행
    while N:
        music_lenth = min(N, max_count)
        music_lenth = _na_13_check(music_lenth)

        """
            [ 중요!! ] 
            다음 노래가 마지막인데 13으로 나누어 떨어질 경우..
            현재 노래에서 한 곡 뺴서 마지막 곡 주기!!
            21 21 12 1 << No!! No!!
            21 20 14 << Good!! Good!!            
        """
        next_n = N - music_lenth
        if (next_n > 0) and (next_n < max_count) and (next_n % 13 == 0):
            music_lenth = _na_13_check(music_lenth - 1)

        # 최종 음반 래핑
        answer += 1
        N -= music_lenth

    return answer


N = int(sys.stdin.readline().rstrip())
L = int(sys.stdin.readline().rstrip())
C = int(sys.stdin.readline().rstrip())

print(_main(N, L, C))

---

 

⏱️ 시간 복잡도

while N : 모든 곡 수록 시 까지 반복 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )