초콜릿 자르기 (feat. 백준, 2163번)

초콜릿 자르기
https://www.acmicpc.net/problem/2163

2163번: 초콜릿 자르기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int ans;
void solution(register int n, register int m){
    if(n == 1 && m == 1)
        return;
    ++ans;
    if(n >= m)
        solution(n / 2, m), solution(n - n / 2, m);
    else
        solution(n, m / 2), solution(n, m - m / 2);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    ans = 0;
    register int N, M;
    cin >> N >> M;
    solution(N, M);
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

1. N과 M 중 더 큰 값을 기준으로 반으로 계속 쪼개면서 총 쪼갠 횟수를 구하는 문제입니다.
2. 재귀적으로 풀이가 가능하므로 이를 이용하여 풀었습니다.