[BOJ] 백준 2163 초콜릿 자르기

Approach

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

N X M 크기의 초콜릿을 1 X 1크기로 자를 때 

필요한 최소 횟수를 구하는 문제이다.

 

자르고 나서는 N X M개 조각이 나오는데

"최소 횟수"는 한쪽 방향으로 스-윽 자르고

다른 방향으로 잘라주는 것이다. (그림 참조)

이때, 자르는 횟수는 N개 행 → N - 1

M개 열 → (M - 1) × N

 

▶ (N - 1) + (MN - N) = MN - 1 = M × N - 1

ex) 5 x 4 크기 일 때, 5 x 4 - 1 = 19

 

C++

#include <stdio.h>

int N, M;

int main() 
{
	// freopen("input.txt", "r", stdin);

	scanf("%d %d", &N, &M);
	
	printf("%d\n", N * M - 1);
}

 

Java

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int temp;
		if(n > m){
			temp = m;
			m = n;
			n = temp;
		}
		System.out.println(   (n-1) + ( (m-1)*n )   );
	}
}