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
'컴퓨터공학 > 알고리즘 _ 문제해결' 카테고리의 다른 글
10799 쇠막대기 백준 알고리즘 문제 스택 (0) | 2017.01.08 |
---|---|
1063 king 킹 시뮬레이션 백준 알고리즘 ! (0) | 2017.01.04 |
1408 24 백준 알고리즘 온라인저지 (0) | 2016.12.26 |
11653 소인수 분해 문제 백준 알고리즘 (0) | 2016.12.22 |
백준 알고리즘 2934 소음 문제! (0) | 2016.12.22 |