백준(BOJ) 1424 새 앨범(Python)

문제 내용.

 

구현 문제.

먼저 한 CD에 최대로 들어갈 수 있는 노래의 개수를 구해야 한다.

노래 사이에는 1초의 공백이 있기 때문에 CD의 길이를 (노래의 길이+1)로 나눈 몫을 구하고, CD의 길이를 (노래의 길이+1)로 나눈 나머지가 노래의 길이와 같다면 몫에 1을 더한다. 이 값이 한 CD에 최대로 들어갈 수 있는 노래의 개수이다.

이때 고려해줄 부분은, CD 하나에 최대로 들어갈 수 있는 노래의 개수보다 전체 노래의 개수가 더 작을 수 있다는 점이다.

따라서 둘 중 더 작은 값을 CD 하나에 최대로 들어갈 수 있는 노래의 개수로 설정한다.

만약 이 값이 13의 배수라면, 이 값에서 -1을 한 값이 한 CD에 최대로 들어갈 수 있는 노래의 개수이다.

 

그렇게 한 CD에 최대로 들어갈 수 있는 노래의 개수를 구한 다음에는 노래의 개수를 이 값으로 나눈 몫을 구한다. 이 값을 ans라고 하자.

그리고 나눈 나머지를 x라고 하자.

만약 x가 0이 아니라면 ans에 1을 더한다. 그 후 x가 13의 배수라면 꽉 차 있는 CD 중 하나에서 노래를 하나 빼고 x개 만큼 들어있는 CD에 노래를 하나 추가해야한다. 이때 노래를 뺀 CD에 들어 있는 노래의 개수도 13의 배수가 아니어야 하고, 노래를 넣은 CD에 들어 있는 노래의 개수도 13의 배수가 아니어야 한다. 그렇게 둘 다 13의 배수가 아닐 때까지 위 작업을 반복한다.

위 작업은 못해도 12번 이내에 종료되며, 이때 노래를 넣은 CD에 들어 있는 노래의 개수가 한 CD에 최대로 들어갈 수 있는 노래의 개수보다 크다면 ans에 1을 더한다.

 

그 후 ans를 출력하면 된다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
"""
import bisect
import math
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
n=int(input())
l=int(input())
c=int(input())
a=c//(l+1)
k=c%(l+1)
if k==l:
    a+=1
a=min(n,a)
if a%13==0:
    a-=1
ans=n//a
x=n%a
k=a
if x!=0:
    ans+=1
    if x%13==0:
        while not (k%13 and x%13):
            k-=1
            x+=1
        ans+=x//a
print(ans)

 

단순 구현이면서 고려해줄 부분도 적당히 있고, 논리로 푸는 문제라 재밌었다.

알고리즘을 어떻게 적용하고 하는 문제들 보다 이런 문제가 훨씬 재밌는 것 같다.