백준 2163번 초콜릿 자르기 : 무작정 대입도 좋지만 증명 하기

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

2163번: 초콜릿 자르기

 

 

📍 | 접근 방식

---

 

이러한 문제의 특징은 규칙성을 찾는 것이다.

사실 요즘 손으로 코딩 하기의 중요성을 느끼고 있다.

 

수능 수학 1등급 맞는 천재가 아니기에 

요즘 나는 이러한 문제가 나오면 항상 손으로 직접 써보면서 규칙성을 찾는다.

 

사실 프로그래밍을 처음 접했을땐 키보드만

두드리면 되는 줄 알았으나 

요즘은 아니더라

 

 

 

 

❓ | 규칙성 찾기

---

 

이게 무슨 석기 시대때 볼 법한 그림이지만

 

위 문제 해결하기 위해 내가 그린 방법이다.

 

나는 테스트 케이스 2가지를 가지고 했다.

 

하나는 3x2 , 4x2 

2가지 경우를 준비했다.

 

그렇게 해서 각각 그림에서 세로로 먼저 자르고 가로로 자르기

가로로 먼저 자르고 세로로 자르기 수를 세어 본 결과

모두 같았다.

 

그렇게 해서 결국 n x m 일때도 내가 생각한 결과랑 같겠지?

라고 생각했고

 

if문 그런거 필요 없이 바로 답을 내주면 된다.

 

 

여기서 풀었다고 넘어가기엔 이 문제에서 배워야 할 게 1가지 더 있다고 생각한다.

 

그냥 막 대입해서 풀었지만

증명을 해보자.

 

초콜릿 조각의 가장 작은 단위는 1x1 이다.

그리고 자르면 항상 조각이 +=1 된다.

 

이 조각들이 모여서 결국에는 N x M 개 있어야 한다.

 

그렇다면 총 필요한 자르기 횟수는 N x M -1 이다.

 

막 대입해서 결과를 찾는 것도 좋지만 그 문제의 수학적 접근도 간단하지만

배워야 한다고 생각하고 이러한 증명 과정이 언제가는 도움이 될 거라 생각한다.

 

 

✅ | 최종 코드

---