백준/DP
(c++)백준 2163번: 초콜릿 자르기
Nimgnoej
2020. 9. 22. 11:03
2163번: 초콜릿 자르기
정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿�
www.acmicpc.net
[풀이]
DP로 풀 수 있다.
먼저 세로로 N번 자르고 각각 조각마다 M번씩 자른다.
점화식
DP[i] = DP[i-1] + N
#include <iostream>
using namespace std;
int N, M;
int DP[301];
void solution() {
DP[0] = N - 1;//처음에 세로로 N-1번 자름
for (int i = 1; i < M; i++)
DP[i] = DP[i - 1] + N;//각각 가로로 N번씩 자름
cout << DP[M - 1] << '\n';
}
int main() {
cin >> N >> M;
solution();
return 0;
}