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

문제 링크

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

풀이 과정

NxM 크기의 초콜릿을 모두 1x1크기의 작은 초콜릿 단위로 쪼개는 데 필요한 최소 연산을 구하는 문제로, 간단한 구현 문제입니다.

아이디어는 아래 그림을 통해 설명하겠습니다.

먼저 NxM 크기의 초콜릿을 세로로 분할하는 데 필요한 연산 횟수를 구해봅니다. 가로 M 크기를 (M-1)번 쪼개 1 크기 단위로 만들 수 있습니다. 이를 통해 우측 그림과 같이 Nx1 크기의 초콜릿이 총 M개 존재하게 됩니다.

다음은 Nx1 크기의 초콜릿 M개를 1x1 크기의 초콜릿 NxM개로 쪼개는 과정입니다. 각 초콜릿을 (N-1)번 쪼개 세로 길이를 1 크기 단위로 만들 수 있습니다. 이미 잘려진 M개의 세로로 긴 초콜릿을 각각 N-1번 쪼개야 하므로, 필요한 연산 횟수는 M(N-1)번 입니다.

따라서, 최종적으로 1x1 크기 단위의 초콜릿으로 만들기 위해선, 세로로 쪼개는 (M-1)번과 가로로 쪼개는 M(N-1)을 더한 NM-1번이 됩니다.

코드

import java.util.Scanner;

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