백준_2163 초콜릿 자르기

링크 https://www.acmicpc.net/problem/2163

2163번: 초콜릿 자르기

접근

재귀적으로 초콜릿을 절반으로 잘라 나간다

절반으로 자르고 나면 2개의 영역이 생긴다

A : 절반으로 잘린 크기 

B : 전체에서 절반을 뺀 크기

수식으로 나타내면 아래와 같다

A = A/2

B = A-(A/2)

 

2차원 배열 DP를 선언하고 아래와 같이 사용한다

DP[i][j] = i*j 크기의 초콜릿을 자르기 위한 절단 횟수

 

만약 y가 x 보다 크다면

dp[i][j] = dp[i/2][j] + dp[i-(i/2)][j] + 1

 

만약 x가 y 보다 크다면

dp[i][j] = dp[i][j/2] + dp[i][j-(j/2)] + 1

 

로 일반화 한다

 

맨 끝에 1을 더해주는 이유는 맨 첫번째 크기에서 한번이 절단이 일어나기 때문이다

큰것 절단 + 작은 크기 절단 횟수 로 생각하면 된다

 

재귀탐색을 구현한다

 

#include <iostream>
#define MAX 301

using namespace std;
int dp[MAX][MAX];
int n, m;
int divide(int y, int x){
    if(dp[y][x] != -1) return dp[y][x];
    if(y >= x){
        int a = dp[y / 2][x];
        int b = dp[y - (y/2)][x];
        if(a == -1 && b == -1){
            return dp[y][x] = divide(y/2, x) + divide(y-(y/2), x) + 1;
        }else if(a == -1){
            return dp[y][x] = divide(y/2, x) + dp[y-(y/2)][x] + 1;
        }else if(b == -1){
            return dp[y][x] = dp[y/2][x] + divide(y-(y/2), x) + 1;
        }else{
            return dp[y][x] = dp[y/2][x] + dp[y-(y/2)][x] + 1;
        }
    }else{
        int a = dp[y][x/2];
        int b = dp[y][x - (x/2)];
        if(a == -1 && b == -1){
            return dp[y][x] = divide(y, x/2) + divide(y, x-(x/2)) + 1;
        }else if(a == -1){
            return dp[y][x] = divide(y, x/2) + dp[y][x-(x/2)] + 1;
        }else if(b == -1){
            return dp[y][x] = dp[y][x/2] + divide(y, x-(x/2)) + 1;
        }else{
            return dp[y][x] = dp[y][x/2] + dp[y][x-(x/2)] + 1;
        }
    }
    return 0;
}

int main(int argc, const char * argv[]) {
    scanf("%d %d", &n, &m);
    for(int y = 0; y < n+1 ; y++){
        for(int x = 0; x<m+1; x++){
            dp[y][x] = -1;
            if(x > 0 && y==1){
                dp[y][x] = x-1;
            }
            if(x==1){
                dp[y][x] = y-1;
            }
        }
    }

    cout<<divide(n, m)<<endl;
    
    
    return 0;
}