d053 - 10970 - Big Chocolate

🔗 前往 ZeroJudge 原題

題目描述

題目描述了Mohammad買了一塊M x N的巧克力，他想將巧克力切成M x N個1x1的小塊，要求找到最少需要切幾刀。

解題思路

將M x N的巧克力切成M x N個1x1的小塊，需要先切成M行，再切成N列。切M行需要M-1刀，切N列需要N-1刀。因此，總共需要 (M-1) + (N-1) = M + N - 2 刀。程式碼直接計算 M * N - 1，因為 M * N 個小塊需要 M * N - 1 刀才能分割開。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include<stdio.h>
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b)>0)
		printf("%d\n",a*b-1);
}