[파이썬(Python)] 백준 2163번 초콜릿 자르기

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

2163번: 초콜릿 자르기

 

 

 

 

백준 2163번은 n*m 크기의 초콜릿을 1*1 크기로 쪼개려면

몇 번 쪼개야 하는 지에 대한 문제입니다.

 

 

 

<코드>

import sys

N, M = map(int, sys.stdin.readline().split())

 

print(N * M - 1)

 

 

sys.stdin.readline() 대신 input()을 활용해도 좋습니다.

 

 

주방에서 채소를 썰 때,

큼직하게 자르고, 큼직한 덩어리를 여러 개 모아 한 번에 잘게 자르는 걸 생각할 수 있는데

그런 방법으로 자르는 게 아닙니다.

 

초콜릿을 한 번 쪼개면, 절반 크기의 초콜릿이 2개가 됩니다.

이 2개를 한꺼번에 쪼개는 게 아니라 각각 쪼개주는 겁니다.

 

 

100(원본 크기)

|

쪼갠다.(1회)

50 / 50

|

각각 쪼갠다.(2회, 총 3회)

25 . 25 / 25 . 25

|

....

 

이런 느낌으로 진행한다고 보면 됩니다.

 

 

귀납적으로 생각해도 좋습니다.

 

아래 예시는 가로 크기가 1이 되도록 먼저 자른 횟수(A)와

가로 크기가 1인 덩어리를 세로 크기 1씩 자른 횟수(B)를 +를 사이로 두고 표현했습니다.

C는 A 덩어리의 개수입니다.

 

초콜릿 = A + B * C

크기 2 * 2 : 1 + 2 * 1 = 3

크기 2 * 3 : 1 + 2 * 2 = 5

크기 3 * 3 : 2 + 3 * 2 = 8

크기 4 * 4 : 3 + 4 * 2 = 15

.

.

.

 

귀납적으로 생각해보면 원본 크기에 -1한 수가 쪼개는 횟수임을 알 수 있습니다.

 

 

 

따라서 N * M - 1을 출력하면 됩니다.

 

 

 

 

코린이 대학생의 풀이였습니다.

풀이에 오류가 있거나 빈약한 부분이 있다면 얼마든지 댓글 남겨주시기 바랍니다.

 

 

 

 

 

https://like-a-happy-cat.tistory.com/ 

키보드 꾹꾹이하는 대학생

 

 

https://blog.naver.com/snake6862

정훈 블로그 : 네이버 블로그