[백준, 파이썬] 2163번 초콜릿 자르기

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

2163번: 초콜릿 자르기

이 문제는 dp 문제로 굉장히 쉬운 문제입니다. 

복잡하게 생각할 필요없이 배열에 수를 채워나가다 보면 규칙이 보이는 문제인데요

먼저 임의의 NxM의 배열에 대해서 쪼개는 갯수를 다음과 같이 채워넣어봅시다.

4x5 사이즈 초콜릿 쪼개기 횟수

규칙은 한눈에 봐도 알수 있을만큼 단순합니다.

즉 첫번째 열의 N번째 요소에 대해서  x m +(m-1)을 수행한다면

(i,m) 번째 요소를 구할 수 있습니다. 즉 우리가 필요한 것은 (5,4), 즉 (m,n)의 요소이므로 

(1,m)*m+m-1을 계산하면 답을 구할 수 있겠네요, 따라서 코드를 작성하면 다음과 같습니다. 

 

m, n = map(int, input().split(' ')) dp = [] def init(dp): for j in range(n): dp.append(j) def solve(dp,m,n): init(dp) print(dp[n-1]*(m)+(m-1)) solve(dp,m,n)