(c++)백준 2163번: 초콜릿 자르기

www.acmicpc.net/problem/2163

2163번: 초콜릿 자르기

[풀이]

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;
}