1 분 소요

1. 문제Permalink

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

  • 수학 문제
// 문제
정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 
초콜릿은 금이  있는 모양을 하고 있으며, 
 금에 의해 N×M개의 조각으로 나눠질  있다.

초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 
이를 위해서 정화는 초콜릿을 계속 쪼개서  N×M개의 조각으로 쪼개려고 한다. 
초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 
초콜릿을 쪼갤 때에는 금이  있는 위치에서만 쪼갤  있다. 
이와 같이 초콜릿을 쪼개면 초콜릿은  개의 조각으로 나눠지게 된다. 
이제 다시  중에서 초콜릿 조각을 하나 들고, 쪼개는 과정을 반복하면 된다.

초콜릿을 쪼개다보면 초콜릿이 녹을  있기 때문에, 정화는 가급적이면 초콜릿을 쪼개는 횟수를 최소로 하려 한다. 초콜릿의 크기가 주어졌을 , 이를 1×1 크기의 초콜릿으로 쪼개기 위한 최소 쪼개기 횟수를 구하는 프로그램을 작성하시오.

// 입력
첫째 줄에  정수 N, M(1  N, M  300) 주어진다.

// 출력
첫째 줄에 답을 출력한다.

// 예제 입력 1 
2 2

// 예제 출력 1 
3

// 예제 입력 2 
1 1

// 예제 출력 2 
0


2. 핵심 아이디어Permalink

  • (n-1) + n(m-1)


3. Python 문제풀이Permalink

import sys
input = sys.stdin.readline

def solve(n, m) :
  return (n-1) + n * (m-1)

if __name__ == "__main__" :
  n, m = map(int, input().split())
  print(solve(n, m))


4. Java 문제풀이Permalink


댓글남기기