백준 2163번 초콜릿 자르기

문제 링크입니다: https://www.acmicpc.net/problem/2163

사실 메모이제이션으로 풀지 않고 간단한 곱셈을 통해 풀 수 있는 문제였습니다.

하지만 문제를 푸는 과정이 중요하기 때문에 다이나믹 프로그래밍으로도 풀어봤습니다.

/*

정화는 N×M 크기의 초콜릿을 하나 가지고 있다.

초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다.

초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다.

이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다.

초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다.

초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다.

이와 같이 초콜릿을 쪼개면 초콜릿은 두 개의 조각으로 나눠지게 된다.이제 다시 이 중에서 초콜릿 조각을 하나 들고, 쪼개는 과정을 반복하면 된다.

초콜릿을 쪼개다보면 초콜릿이 녹을 수 있기 때문에, 정화는 가급적이면 초콜릿을 쪼개는 횟수를 최소로 하려 한다.

초콜릿의 크기가 주어졌을 때, 이를 1×1 크기의 초콜릿으로 쪼개기 위한 최소 쪼개기 횟수를 구하는 프로그램을 작성하시오.

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int INF = 987654321;

int row, column; //가로 세로

int cache[301][301];

 

//간단한 버전(몇번 그려보면 알 수 있다)

int minCut(void)

{

        return (row * column) - 1;

}

 

void preCalculate(void)

{

        memset(cache, -1, sizeof(cache));

        for (int i = 1; i <= 300; i++) //가로가 1인 경우

               cache[1][i] = i - 1; //(세로의 길이 - 1) 만큼 쪼갬

        for (int i = 1; i <= 300; i++) //세로가 1인 경우

               cache[i][1] = i - 1; //(가로의 길이 - 1) 만큼 쪼갬

}

 

int minCut(int row, int column)

{

        if (row <= 0 || column <= 0) //범위 벗어나면

               return INF;

        int &result = cache[row][column];

        if (result != -1)

               return result;

 

        int cutNum = INF;

        //가로를 나누어 계산

        for (int i = 1; i <= (row + 1) / 2; i++)

               cutNum = min(cutNum, minCut(i, column) + minCut(row - i, column));

        //세로를 나누어 계산

        for (int i = 1; i <= (column + 1) / 2; i++)

               cutNum = min(cutNum, minCut(row, i) + minCut(row, column - i));

        //함수를 호출했다는 것은 나눈다는 뜻이므로 1 더해줌

        return result = ++cutNum;

}

 

 

int main(void)

{

        cin >> row >> column;

        if (row < 1 || row>300 || column < 1 || column>300)

               exit(-1);

        preCalculate();

        //cout << minCut() << endl;

        cout << minCut(row, column) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~