Today's Algorithm(2019-03-13)

baekjoon2163. 초콜릿 나누기

다이나믹 프로그래밍을 연습하려고 이 문제를 뽑았지만 수학 문제에 더 가까운 것 같습니다. 생각할 부분도 딱히 없어서 가볍게 정리하고 넘어가겠습니다.

N * M길이의 초콜릿을 효율적으로 나누기 위해선 한번 금을 가를 때 최대한 길게 나누는게 좋겠죠? 가로로 나눈다고 생각해봅시다(세로 나누어도 결과는 같습니다). 그렇다면 가로가 N이라면 M - 1 번 나눌 수 있을 것입니다. 그렇다면 이젠 각 줄 안을 다 잘라야 합니다. 그 개수는 M - 1 줄에 N개씩 있으니 (M - 1) * N 이구요. 결과적으로 (M - 1) * N(M - 1) = NM - 1이 됩니다. 세로를 먼저 나눈다고 하더라도 NM - 1로 계산하는 건 같습니다.

뭔가 더 효율적인 방법이 있을 것 같지만 몇 번 그려보신다면 이것이 문제에 주어진 조건 내에서 최선이라는 것을 알 수 있을 것입니다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] arr = toArray(br.readLine());
        System.out.println(arr[0] * arr[1] - 1);
    }

    private static int[] toArray(String readLine) {
        String[] arr = readLine.split(" ");
        return new int[]{Integer.parseInt(arr[0]), Integer.parseInt(arr[1])};
    }
}