[백준 14607번] 피자 (Large) (C++)

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

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

ll N;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;

    cout << N*(N-1)/2; //점화식

    return 0;
}

 

백준 14606번과 유사하지만 N의 범위 때문에 14606번을 풀었던 점화식을 그대로 사용한다면 메모리 초과가 발생하는 문제이다.

참고링크 : https://blob-thinking.tistory.com/386

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

 

계속 실패하는 탓에 따로 검색해본 결과 새로운 점화식을 알 수 있었다.

<기존 점화식>
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

6
5 + 10 = 15 (6*5/2)

7 
6 + 15 = 21 (7*6/2)

8
7 + 21 = 28 (8*7/2)