[C++] BOJ 2163 - 초콜릿 자르기

#include <iostream>

int main() {
	int N,M;
	int D[301][301];
	
	scanf("%d %d",&N,&M);
	
	for(int i=1;i<=N;i++) 
		D[i][1] = i-1;
	for(int i=1;i<=M;i++) 
		D[1][i] = i-1;
	
	for(int i=2;i<=N;i++) {
		for(int j=2;j<=M;j++) {
			if(i%2 == 0) D[i][j] = 1+D[i/2][j]*2;
			else D[i][j] = 1+D[i/2][j]+D[i-i/2][j];
		}
	}
	
	printf("%d",D[N][M]);
}

DP를 사용해서 풀어보았습니다.

D[i][j] = i x j 의 초콜릿을 자르는데 필요한 횟수

1 x n 또는 n x 1 의 초콜릿을 자르는데 필요한 횟수는 n-1번!

<점화식>

가로 길이가 짝수이면 절반으로 자르는데 필요한 1번을 더하고 나뉜 두조각을 자르는데 필요한 횟수를 더합니다.

가로 길이가 홀수이면 가로길이를 i/2와 i-(i/2)로 나누어 자르는데 필요한 1번을 더하고 위와 같이 나뉜 두조각을 더합니다.

-> 더 쉽게 푸는 법(드래그)

이 문제를 다풀고 뒤늦게 알아챘던거지만 사실은 DP를 쓸 필요 없이 그냥 N*M-1하면 답이였네요 ㅎㅎ DP로 풀었다는 것에 의의를 두..려.. 합니다ㅠㅠ