백준 2163 초콜릿자르기 풀이

사용언어

Visual studio 2019 C++

생각하기

다이나믹 프로그래밍, 수학

문제를 읽고 예시들을 생각해보면 수학적으로 접근해서 풀 수 있다.

1. 2 X 4 -> 7번으로 1X1로 쪼갤 수 있다.

2. 3 X 4 -> 11번으로 1X1로 쪼갤 수 있다.

=> 종합해보면 N * M - 1로 풀 수 있다.

[2163 풀이]

Math

#include <iostream>
using namespace std;
int N, M;

int main() {
	cin >> N >> M;

	cout << N * M - 1 << "\n";
}

DP

#include <iostream>
#define MAX 301
#define endl "\n"
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); 
	cout.tie(0);

	int N, M;
	cin >> N >> M;

	// ex) 4 X 2

	int DP[MAX];
	DP[0] = N - 1; // 가로로 3(N-1)만큼 자른다
		       // 1 X 2 -> 4(N)개 생성

	for (int i = 1; i < M; i++)
		DP[i] = DP[i - 1] + N; 
		// 세로로 1번(2(M)를 포함안하므로) 4(N)개생성되었으므로 자른다

	cout << DP[M - 1] << endl;
}