[C++] 백준 2163번 초콜릿 자르기

n*m크기의 초콜릿을 n*m개가 될때까지 쪼개는 문제입니다.

예를들어 2*2 = 4

4조각의 초콜릿을 반으로 자르면 2조각이 2개 생길것입니다.  ( 4 ) -> ( 2 2 )

거기서 2조각 짜리를 한번 자르면 1조각이 2개 2조각이 1개가 생깁니다. ( 2 2 ) -> ( 1 1 2 )

마저 2조각을 한번 더 자르면 1조각이 4개가 됩니다. ( 1 1 2 ) -> ( 1 1 1 1 )

 

여기서 2조각을 한조각으로 자르는 과정을 2번 반복하게 됩니다.

조각 수가 커진다면 더 많은 반복이 일어나게 될것입니다.

이를 줄이기 위해 다이나믹 프로그래밍 기법을 사용해서 문제를 풀었습니다.

 

memo라는 배열에 몇조각이였을때 몇번 나눠야된다는 것이 입력이 되면

그 후로는 같은 조각 수가 나왔을때 이미 나온 결과를 가져오면서 반복된 작업을 생략할 수 있습니다.

 

재귀함수를 통해서 한번 함수를 통할때마다 값을 1씩 증가해주면서

마지막에는 모든값들이 더해지면서 총 몇번 쪼갰는지를 출력해주었습니다.

 

#include <iostream>
using namespace std;

int choco(int num, int memo[]) {
   if (num == 1) {
      return 0;
   }
   if (memo[num] != 0) {
      return memo[num];
   }
   if (num % 2 == 0) {
      memo[num] = (choco(num / 2, memo) * 2)+1;
   }
   else {
      memo[num] = choco(num / 2, memo) + choco(num/2+1, memo)+1;
   }
   return memo[num];   
}
void init(int memo[]) {
   for (int i = 0; i<100; i++) {
      memo[i] = 0;
   }
}
int main(void)
{
   int memo[100000];
   int num;
   int x, y;
   int value;
   init(memo);
   cin >> x;
   cin >> y;
   num = x * y;
    value = choco(num, memo);
   cout << value << endl;
   
   return 0;
}