[백준] 2163 초콜릿 자르기

https://www.acmicpc.net/problem/2163

2163번: 초콜릿 자르기

 

분할 정복 문제

 

항상 최소가 되려면, 반으로 쪼개면 된다.

 

[풀이]

1. 가로가 1이 아니라면 반으로 쪼개자

2. 가로가 1이고, 세로가 1이 아니라면 세로를 반으로 쪼개자

매번 쪼갤 때마다, count를 올려주자.

 

divide_i : 세로쪼개기

divide_j : 가로쪼개기

#include <iostream>
#include <vector>

using namespace std;
int answer;

void divide_i(int x) {
	if(x == 1)
		return;

	else {
		answer++;
		divide_i(x/2);
		divide_i(x-x/2);
	}
}

void divide_j(int y, int x) {
	if(y == 1) {
		if(x != 1) {
			answer++;
			divide_i(x/2);
			divide_i(x - x/2);
		}
		return;
	}

	else {
		answer++;
		divide_j(y/2, x);
		divide_j(y - y/2, x);
	}
}


int main() {
	int n, m;
	scanf("%d %d", &n, &m);

	if(n != 1) {
		answer++;
		divide_j(n/2, m);
		divide_j(n - n/2, m);
	}
	else if(m != 1) {
		answer++;
		divide_i(m/2);
		divide_i(m - m/2);
	}

	printf("%d\n", answer);
	return 0;
}