[백준 14606번] 피자 (Small) (C++)

문제링크 : https://www.acmicpc.net/problem/14606

14606번: 피자 (Small)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int dp[11];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    dp[1] = 0; //나누기 불가능
    dp[2] = 1; //(1, 1)
    
    for(int i=3; i<=N; i++)
    {
        dp[i] = dp[i-1] + (i-1); //점화식
    }

    cout << dp[N];
    return 0;
}

 

높이가 1이라면 나누기가 불가능하므로 0, 높이가 2라면 나누는 경우가 1*1 밖에 없으므로 1로 각각 초기화해주고 시작한다.

 

이후 점화식은 직접 적어보면서 찾아보았다.

3 -> (1, 2) (2, 1) 2 -> (1, 1) 
1*2 + 1*1 = 3

4 -> (1, 3) (2, 2) (3, 1)
1*3 + 1*2 + 1*1 = 6

5 -> (1, 4) (2, 3) (3, 2) (4, 1)
1*4 + 1*3 + 1*2 + 1*1 = 10

위를 보면 이전값 + 현재 i-1인 것을 알 수 있음
나누는 케이스가 여러가지지만, 나누고 계산하다보면 결국 같은 값임
따라서 첫 번째 케이스를 토대로 점화식 작성 (ex (1,2) (1,3) (1,4)...)