백준 2163 C++ 초콜릿 자르기

첫 PS 게시물이다!ㅎㅎㅎㅎ

그런 만큼 쉬운 문제로 뇌풀기를 좀 해봤다.

백준 문제 링크 : https://www.acmicpc.net/problem/2163 

2163번: 초콜릿 자르기

초콜릿 자르기

문제

정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다.

초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 같이 초콜릿을 쪼개면 초콜릿은 두 개의 조각으로 나눠지게 된다. 이제 다시 이 중에서 초콜릿 조각을 하나 들고, 쪼개는 과정을 반복하면 된다.

초콜릿을 쪼개다보면 초콜릿이 녹을 수 있기 때문에, 정화는 가급적이면 초콜릿을 쪼개는 횟수를 최소로 하려 한다. 초콜릿의 크기가 주어졌을 때, 이를 1×1 크기의 초콜릿으로 쪼개기 위한 최소 쪼개기 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M(1≤N, M≤300)이 주어진다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

2 2

예제 출력 1

3

문제 핵심 포인트

1. 연속적인 상황이고, 길이 조건만 바꿔주면 되는 것이므로 재귀함수를 사용해보자.

2. 1 x 1 크기가 되면 더 이상 자르면 안 되기 때문에 재귀함수를 탈출할 조건을 고려하자.

3. n이나 m이 홀수인 상황을 고려하자.

4. 복잡한 수학 공식 사용하는 것이 아니므로 놓치는 부분이 있는지 걱정안해도된다.

 

문제 해설

쉬운 문제다. 어렵게 고민하지 않아도 된다. 재귀함수를 이용하여 문제를 해결했다.

n x m 에서 둘 중에 큰 놈을 반으로 자르고, 두 덩어리를 다시 자르고, 또 다시 자르고 ......

자를 수 없을 때까지 자르면서 자른 횟수를 count하면 된다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int answer;


void cut(int cur_n, int cur_m){
    //cout << "now n : " << cur_n << "now m : " << cur_m << '\n';
    
    if(cur_n == 1 && cur_m == 1) return; // n,m 둘다 1일 경우 재귀함수 정지
    else if(cur_n == 1){ // 현재 n이 1일경우 m쪽만 분할해주면 됌.
        answer++;
        if(cur_m%2 == 1){ //현재 m이 홀수라면
            cut(cur_n, cur_m/2);
            cut(cur_n, cur_m/2 + 1);
        }
        else{ // 현재 m이 짝수라면
            cut(cur_n, cur_m/2);
            cut(cur_n, cur_m/2);
        }
    }
    else if(cur_m == 1){ // 현재 m이 1일경우 n쪽만 분할해주면 됌.
        answer++;
        if(cur_n%2 == 1){ //현재 n이 홀수라면
            cut(cur_n/2, cur_m);
            cut(cur_n/2 + 1, cur_m);
        }
        else{ // 현재 n이 짝수라면
            cut(cur_n/2, cur_m);
            cut(cur_n/2, cur_m);
        }
    }
    else{ //일반적인 경우
        answer++;
        if(cur_n > cur_m){
            if(cur_n%2 == 1){ //현재 n이 홀수라면
                cut(cur_n/2, cur_m);
                cut(cur_n/2 + 1, cur_m);
            }
            else{ // 현재 n이 짝수라면
                cut(cur_n/2, cur_m);
                cut(cur_n/2, cur_m);
            }
        }
        else{
            if(cur_m%2 == 1){ //현재 m이 홀수라면
                cut(cur_n, cur_m/2);
                cut(cur_n, cur_m/2 + 1);
            }
            else{ // 현재 m이 짝수라면
                cut(cur_n, cur_m/2);
                cut(cur_n, cur_m/2);
            }
        }
    }
}


int main(int argc, char* argv[]) {
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    cut(n,m);
    
    cout << answer << '\n';
	
	return 0;
}