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

: solved.ac - bronze 1

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

2163번: 초콜릿 자르기

 

 

예제 입력1

2 2

 

예제 출력1

3

 

예제 입력 2

1 1

 

예제 출력 2

0

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	printf("%d", n * m - 1);
	return 0;
}

---

해설

: 수학적 규칙. n*m -1만 계산하면 답이 나온다.

(문제의 알고리즘 분류도 '수학' '사칙연산' 이다. 문제가 의도한 정석 풀이법도 이 방법이 맞는 듯.)

 

어려워 보이는 문제의 설명에 비해 허무할 정도로 간단한 정답 코드이다.

코딩을 어느 정도 배운 사람들은 보통 이 문제를 탐색이나 DP(Dynamic Programming)으로 접근하곤 하나

(횟수가 최소가 되도록 자르는 지점을 탐색하는 등)

기실 초콜릿 조각들을 여럿 겹쳐서 자를 수 있다는 조건이 없는 이상

최소고 뭐고 가능한 횟수의 경우의 수는 한 가지밖에 없다.

 

초콜릿은 처음에는 한 조각이다. 한 번 쪼개면 어떤 식으로 쪼갰든지 두 조각이 된다.

또 한 번 쪼개면 세 조각, 한 번 더 쪼개면 넷... 이런 식으로 '한 번 쪼개면 무조건 한 조각이 늘어나는' 규칙이 있다.

n*m의 격자대로 모든 조각이 나눠지길 원한다면, (한 조각에서 시작하므로) 당연히 n*m-1번 쪼개야 한다.

 

https://www.acmicpc.net/board/view/48119

글 읽기 - [스포] dp문제라서 dp로 풀었는데.. 허탈하네요

 

위는 DP로 푼 코드의 예시이다. 보통 유사한 다른 문제에서는 이런 접근법을 쓴다는 정도만 참고하고 넘어가자.

일견 알고리즘적으로 해결하기 어려운 문제도 수학적 규칙을 조금만 도입하면 손쉽게 풀린다는 것을 보여주는 예시가 되겠다.