[백준] 2163번. 초콜릿 자르기
[백준] 2163번. 초콜릿 자르기
1. 문제
정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다.
초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 같이 초콜릿을 쪼개면 초콜릿은 두 개의 조각으로 나눠지게 된다. 이제 다시 이 중에서 초콜릿 조각을 하나 들고, 쪼개는 과정을 반복하면 된다.
초콜릿을 쪼개다보면 초콜릿이 녹을 수 있기 때문에, 정화는 가급적이면 초콜릿을 쪼개는 횟수를 최소로 하려 한다. 초콜릿의 크기가 주어졌을 때, 이를 1×1 크기의 초콜릿으로 쪼개기 위한 최소 쪼개기 횟수를 구하는 프로그램을 작성하시오.
2. 입력
첫째 줄에 두 정수 N, M(1≤N, M≤300)이 주어진다.
3. 출력
첫째 줄에 답을 출력한다.
4. 풀이
- 최솟값은 사기였다.
- 어떻게 자르는 게 최소일까 다양하게 고민해봤는데 어떻게 잘라도 같은 횟수가 나온다.
아니면 말고
N X M
이니까N-1
의 금과M-1
개의 금이 있다.N-1
번 쪼개서 초콜릿을1 X M
초콜릭N
개로 만들어주자.1 X M
초콜릿을1 X 1
초콜릿으로 만들려면M-1
번 쪼개야 한다.M-1
번 쪼갤 초콜릿이N
개 있다.- 총 횟수는
N-1 + (M-1) *N
이다.
5. 코드
#include <iostream>
using namespace std;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
cout << (n - 1) + (m - 1) * n << "\n";
}
역대급으로 짧네
Author And Source
이 문제에 관하여([백준] 2163번. 초콜릿 자르기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@e7838752/boj2163저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)