[성실코딩 7일차] 백준 #2163 초콜릿 자르기 / 재귀, DP

처음에 문제 접했을 때는 "재귀함수 호출" 구조 풀면 되겠다 생각햇음.

그리고 풀고나서 과정들 적는데 왜 DP인지 이해갔음! 

그 전에 계산했던 부분이 재사용되는 구조였음. 비슷한 문제로 피보나치 수 구하는 문제가 있음

풀이 과정

1. 재귀적으로 호출

#include<iostream>

using namespace std;

int cnt = 0;

void DividenCount(int n, int m) {
	if (n==1 && m==1) { // 탈출조건
		return;
	}

	if (n!=1) { // 행을 나눠주기
		cnt++;
		DividenCount(1,m);
		DividenCount(n-1,m);
	}
	else if(m!=1) { // 열 나눠주기
		cnt++;
		DividenCount(n, 1);
		DividenCount(n, m-1);
	}
}

int main(void) {

	int n, m;
	cin >> n >> m;
	
	DividenCount(n, m);
	
	cout << cnt << endl;

	return 0;
}

2. DP

#include<iostream>

using namespace std;

int DP[301][301] = {0,};
int cnt = 0;

int DividenCount(int n, int m) {

	if (DP[n][m]!=0) {
		return DP[n][m];
	}

	if (n==1) {
		return DP[n][m] = m-1;
	}
	else if (m==1) {
		return DP[n][m] = n-1;
	}

	return DP[n][m] = DividenCount(1, m) + DividenCount(n - 1, m) + 1;
	
}

int main(void) {

	int n, m;
	cin >> n >> m;
	
	// 초기화
	DP[1][1] = 0;

	cout << DividenCount(n, m) << endl;

	return 0;
}