[ 백준 2163 ] 초콜릿 자르기 (C++)

백준의 초콜릿자르기(2163) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 초콜릿의 가로, 세로길이가 주어진다. 이 때, 이 초콜릿을 1x1크기로 만들려면 총 몇번을 잘라야 하는지

  구하는 문제이다.

[ 문제풀이 ]

1. 백준사이트에서 DP로 분류되어 있긴 한데, 뭔가 점화식을 만들 필요도 없을만큼 간단한 문제이다.

   쉽게 생각하면 된다.

   가로가 M, 세로가 N일 때, M = 2, N = 2라고 가정해보자. 생각을 하면서 읽으면 쉬울 것이다.

   그럼 2x2 크기의 정사각형 형태의 초콜릿이 있을 것이다.

   여기서 먼저 세로의 길이를 1로 만들어 보자. 지금 세로의 길이가 2이기 때문에, 한 번만 자른다면 2x1 짜리 초콜릿

   2개가 생길것이다. 그럼 세로의 길이가 3이면? 세로를 1로 만들기 위해서 2번을 짤라야할 것이다.

   그럼 세로가 N이면 ? N - 1번을 잘라야 할 것이다.

  

   아마도 이런식으로 잘리게 될 것이다.

   이제 가로를 1로 만들어보자. 다시 M = 2, N = 2로 돌아가서, 위의 그림처럼 세로의 길이를 1로 만든 상태이고

   전체 크기를 1x1로 만드는 과정을 생각해보자. 위의 그림을 보면서 생각해보면, 2번을 더 자르면 된다.

   왜 2번일까? M을 1로 만들기 위해서는 한 조각 당 M - 1번을 잘라야 할 것이다.

   이해가 잘 되지 않는다면, 위의 그림에서 세로를 1로 만드는 과정이 아닌, 가로를 1로 만들면 어떤 모양이 될지를

   한번 생각해보자. 위의 그림의 결과와는 반대로 세로로 길쭉한 직사각형이 아마 나올 것이다.

   즉, 가로가 2일 때, 1로 만들기 위해서는 1번을, 가로가 3일 때는 2번을, 가로가 M일 때는 M-1번을 잘라야 할 것이다.

   하지만 식이 성립하지가 않는다. 분명 가로가 M 일 때 M-1번을 잘라야 한다고 했는데, M = 2일 때 M-1번이니까

   1번만 자르면 되는데, 위에서 2번을 자르면 된다고 하지 않았는가?!

   너무나도 당연한 얘기를 주구장창 하고 있다. 2조각 나있는 조각 중 한 조각만 자르는데 1번, 다른 한조각 자르는데 1번

   총 2번이 걸릴 것이다.

   그럼 3조각 나있는 경우는 ? 3번을 잘라야 할 것이다. 4조각은 ? 4번, N조각은? N번을 잘라야 할 것이다.

  

   그럼 정리를 한번 해보자.

   우리는 먼저 세로를 1로 만들기 위해서 N-1번을 잘라야 했고,

   가로를 1로 만들기 위해서 M-1번을 N번 잘라야 한다.

   이를 식으로 표현해보면 N - 1 + N*(M - 1)이 된다.

   정리해보면 N - 1 + NM - N = NM-1.

   즉, 이 문제의 답은 N * M - 1이 답이다.

   DP문제임에도 점화식도 필요없이 조금만 생각하면 쉽게 풀 수 있는 문제였다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 300
using namespace std;
 
int N, M;
 
void Input()
{
    cin >> N >> M;
}
 
void Solution()
{
    cout << N * M - 1 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}