https://www.acmicpc.net/problem/2163
문제
> NxM 크기의 초콜릿이 있는데 NxM개의 조각으로 나누어 질 수 있고 금이 그어져 있는데 금의 위치에서만 쪼갤 수 있다.
> 초콜릿을 1x1 크기로 나눌 때 최소한의 쪼개기 횟수를 구해라.접근
조각이 적은 경우를 먼저 생각하며 조각 을 나누는 수식을 생각하고 가로먼저 나눌 때 세로먼저 나눌 때의 식과 결과가 다른지 검증한다. 검증에 따라 결과를 내는 수식을 세워 출력한다.
문제해결
> N,M에 대해서 나눌 떄 금은 각각 N-1, M-1개 그어져 있다. 가로, 세로 어디로 먼저 나누든지 결과에는 차이가 없으므로 먼저 N-1(혹은 M-1)번 쪼개게 된다.
> 쪼개고 나면 금이 M-1개 그어진 초콜릿 N 덩어리가 있으므로 M-1번씩 N번 쪼개야한다. 즉, N x M-1
> 두 횟수를 더한다.코드
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M;
cin >> N >> M;
cout << N * M - 1 << '\n';
}
후기
한 줄로 끝나서 오히려 생각이 많아져 이것 저것 경우를 따져보고 고려해 보았다.
최종적으로 N-1 + N x (M-1)이라는 수식이 나와 끝내려 했으나 해당 수식을 풀어 정리하면 N x M -1로 정리가 된다는걸 알았다. 연산을 더 줄이고 메모리를 줄일 수 있다.
역시 방심하지 말고 수식이 나오면 수식도 최소 연산으로 정리하자.
