[BOJ] 백준 1424 - 새 앨범

문제 링크

www.acmicpc.net/problem/1424

1424번: 새 앨범

 

풀이

시디에 들어가는 곡의 수가 13의 배수이면 안된다는 조건 때문에 생각없이 풀면 여러번 틀릴 수 있는 문제입니다.

 

우선 한 시디에 들어갈 수 있는 곡의 수 $k$의 최댓값을 구해봅시다.

 

노래 한 곡을 추가할 때마다 1초의 시간을 사이에 끼워야합니다.

노래의 길이 $l$, CD의 용량 $c$에 대해, $k$는 다음 부등식을 만족합니다.

$l + (k-1)(l+1) \leq c$

$k(l+1) \leq c+1$

$k \leq \dfrac{c+1}{l+1}$

 

$k$의 최댓값을 구했으니 1부터 최댓값 사이의 수를 모두 대입해볼 수 있습니다.

 

이때 단순히 $k$가 13의 배수인지만 판별하면 틀립니다. 

$n$개의 노래를 $k$개씩 시디에 집어넣고 딱 나누어떨어지지 않아 남은 노래의 개수를 $r$이라 합시다.

이 $r$을 처리하는 방법도 생각을 해야합니다. 

$r$이 13의 배수일때, 다른 시디에서 노래를 나눠주어 13의 배수가 아니게 만드는 경우와, 그게 불가능하여 시디를 하나 더 사용해야 하는 경우가 있습니다.

 

만약 $k = r+1$이라면, 어떤 시디에서 노래를 나눠주어도 항상 13의 배수가 생기게 됩니다. 따라서 시디를 하나 더 사용해야합니다.

그 외에는 항상 노래를 나눠주어 모든 시디의 곡 수가 13의 배수가 아니도록 만들 수 있습니다.

 

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;
using ll = long long;

ll n, l, c;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> l >> c;
    ll ans = INF;
    for (ll k = (c + 1) / (l + 1); k > 0; k--) {
        if (k % 13 == 0) continue;
        ll r = n % k;
        if (r > 0) {
            if (r % 13 == 0 && r + 1 == k) r = 2;
            else r = 1;
        }
        ans = min(ans, n / k + r);
    }
    cout << ans;
}