[Java] 백준알고리즘 #2163 초콜릿 자르기

백준알고리즘 #2163 초콜릿 자르기 문제

 

위 문제의 공식을 도출하기가 헷갈려서 그렇지 굉장히 간단한 문제이다.

 

발그림 죄송..

위와 같은 크기의 초콜릿이 있다고 하자. M은 9개, N은 7개이다.

 

먼저 M 또는 N개만큼 나눈다. 어느쪽으로 나누어도 결과는 똑같이 나온다. N개로 나눈다고 하자.

N개로 나누기 위해서는 가로선을 따라 쪼개면 되는데 이 횟수는 N - 1, 즉 6번이 된다.

 

그리고 N개로 나누어진 초콜릿들을 각각 M개로 나누어야 한다. 이 횟수는 N x (M - 1)이다.

두 횟수를 더하면 N - 1 + N x (M - 1) 이 된다.

이는 N - 1 + (N x M) - N과 같으므로 N을 지워주면 N x M - 1 이라는 아주 간단한 공식이 나오게 된다.

 

이 공식을 대입하여 코드를 작성해보면 다음과 같다.

import java.util.Scanner;

public class Back2163 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int m = sc.nextInt();
		int count = 0;

		count = m * n - 1;
		System.out.println(count);

	}

}