문제
N x M 크기의 초콜릿을 1 x 1 조각으로 쪼개려면 최소 몇 번 잘라야 하는지 구하라.
입력
첫째 줄에 N과 M이 주어진다.
출력
최소 쪼개기 횟수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 2 | 3 |
풀이
N x M 초콜릿을 1 x 1로 만드는 최소 횟수는 N*M - 1이다.
- NM개의 조각을 만들려면 NM - 1번 잘라야 한다
- 한 번 자를 때마다 조각이 정확히 1개 증가하기 때문이다
핵심 아이디어: 1개에서 시작하여 NM개가 되려면 정확히 NM-1번의 절단이 필요하다.
코드
package day599;
import java.io.*;
import java.util.*;
public class Day595BOJ2163초콜릿자르기 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
System.out.print(Integer.parseInt(st.nextToken()) * Integer.parseInt(st.nextToken()) - 1);
}
}복잡도
- 시간: O(1)
- 공간: O(1)