2163 초콜릿 자르기 Dynamic Programing 백준

2163 초콜릿 자르기 Dynamic Programing

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

백준 온라인 저지

C++ 배우기 (1~50)

문제집을 풀면서 조금 생각해야되는 문제라고 생각하여 글을 쓴다.

Dynamic Programing 동적 프로그래밍을 이용하여 풀었다.

초콜릿을 쪼갤때마다, 쪼갠 크기에서 1X1 초콜릿이 될때까지의 횟수를 2차원 배열에 저장 했다.

1X1 이면 0이며, 가로로 인덱스가 1씩 증가할때마다 1씩 증가 시켜준다. 그 외의 초콜릿은 그 열의 초콜릿 갯수만큼 더 해주면 된다.

2X2 는 1X2 에서 2를 더 해주면 총 3번 쪼갠값 ! 

아이 몰라 소스코드는 아래에 !

#include <iostream>

using namespace std;

int main(){

    int cho[301][301]={0,};

    int n=0,m=0;

    cin >> n >> m;

    for(int i = 0; i < n; i++){

        for(int j = 0; j < m; j++){

            if((i==0 && j>0))

                cho[i][j] = cho[i][j-1]+1;

            else if(j==0 && i>0)

                cho[i][j] = cho[i-1][j]+1;

            else if(i>0 && j>0)

                cho[i][j] = cho[i][j-1] + (i+1);

            

            for(int n1 = 0; n1 < n; n1++){

                for(int n2 = 0; n2 < m; n2++){

                    cout << cho[n1][n2] << " ";

                }

                cout << endl;

            }

        }

    }

    cout << cho[n-1][m-1];

    return 0;

}

// 1 2 3

//10 1 2

//21 3 5

//32 5 8