백준 24456 (C++) 초콜릿 훔쳐 먹기

최초 업로드: 2025-10-19 14:59:54

최근 수정 시간: 2025-10-19 15:22:09

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 초콜릿 훔쳐 먹기

[문제 링크](https://www.acmicpc.net/problem/24456)

## 문제 설명

초콜릿을 좋아하는 인규는 연진이의 초콜릿을 하나씩 훔쳐먹으려고 한다. 연진이는 $N \times M$ 크기의 초콜릿을 가지고 있다. 인규는 여기서 하나를 훔쳐먹고 $M \times N - 1$개의 초콜릿을 만들 것이다. 그런데 인규가 초콜릿을 하나를 훔쳐먹으면 모양이 바뀌게 되므로 초콜릿을 훔쳐먹었다는 사실이 들통나게 될 것이다! 따라서 인규는 남은 초콜릿을 재배열해 직사각형 형태로 만들 것이다.

이때 주의해야 할 점은, 새로 만든 초콜릿의 가로와 세로 길이의 차이 $\texttt{D}_\texttt{new}$가 처음 초콜릿의 가로와 세로의 차이 $\texttt{D}_\texttt{old}$와 크게 변함이 없어야 훔쳐 먹었다는 티가 나지 않는다. 따라서 인규는 $|\texttt{D}_\texttt{new} - \texttt{D}_\texttt{old}|$를 $K$ 이하로 유지하며 최대한 많은 초콜릿을 먹을 것이다.

아래 그림을 예로 들어 보자.

$K=5$일 때 $4 \times 4=16$개의 초콜릿이 있다. 처음 초콜릿의 가로와 세로 길이가 동일하므로 $\texttt{D}_\texttt{old}$를 계산하면 $0$이 된다.

만약 인규가 초콜릿을 하나 먹고 $3 \times 5$ 모양으로 재배열한다면, $\texttt{D}_\texttt{new} = |3 - 5| = 2 \le \texttt{D}_\texttt{old} + K = 5$이 되므로 초콜릿을 하나 먹을 수 있다.

여기서 초콜릿을 하나 더 먹게 된다면 $2 \times 7$ 모양으로 재배열이 가능하다. 이때 $\texttt{D}_\texttt{new} = |2-7| = 5 \le \texttt{D}_\texttt{old} + K = 5$이므로 초콜릿을 하나 더 먹을 수 있다.

여기서 초콜릿을 하나 더 먹게 된다면 $1 \times 13$ 모양으로만 재배열이 가능하다. 이때 $\texttt{D}_\texttt{new} = |1-13| = 12 > \texttt{D}_\texttt{old} + K = 5$으로 규칙을 만족하지 못하므로 세 번째 초콜릿은 먹을 수 없다.

한 가지 예를 더 보자.

$K=4$일 때 $4 \times 5 = 20$개의 초콜릿이 있다. 처음 초콜릿에서 $\texttt{D}_\texttt{old}$를 계산하면 $1$이 된다.

만약 인규가 초콜릿을 하나 먹게 된다면 $19$개의 초콜릿을 직사각형 모양으로 만들어야 하는데 가장 작은 $|\texttt{D}_\texttt{new} - \texttt{D}_\texttt{old}|$는 $18$이며, $K$보다 크므로 인규는 초콜릿을 하나도 먹을 수 없다. 인규가 초콜릿을 $2$개 먹은 후에 $3 \times 6$ 모양으로 배열하면 $|\texttt{D}_\texttt{new} - \texttt{D}_\texttt{old}|$는 $K$보다 작은 $2$가 되지만, 한 번에 하나의 초콜릿만 먹을 수 있으므로 이 상태에 도달하지 못한다.

$N,\ M,\ K$가 주어질 때, 인규가 몰래 먹을 수 있는 연진이의 초콜릿의 개수를 구하시오.

단, 인규가 모든 초콜릿을 먹게 되면 연진이가 눈치챌 수 있으므로, 최소 $1$개의 초콜릿은 남겨놓아야 한다.

## 입력

첫 번째 줄에는 세 정수 $N,\ M,\ K$가 공백으로 구분되어 입력된다. ($1 \le N,\ M \le 10\,000$, $0 \le K \le N \times M$)

## 출력

인규가 몰래 먹을 수 있는 초콜릿의 수를 출력한다.

## 풀이
초콜릿을 먹을 수 있는지 없는지 거의 빠르게 판단하여 연산 횟수가 그리 크지 않기 때문에 브루트포스로 풀립니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, k; cin >> n >> m >> k;

int cnt=0;
 for(int i=1;i<=n*m;i++) {
 int cur = n*m-i;

bool chk=false;
 for(int j=1;j*j<=cur;j++) {
 if(cur%j==0 && abs(abs(m-n)-abs(j-cur/j))<=k) {
 chk=true;
 break;
 }
 }
 if(!chk) break;
 cnt++;
 }
 cout << cnt;
}
```