<repo_name>E-Sangho/Baekjoon_Algorithm<file_sep>/9461.cpp
#include <iostream>

using namespace std;

int sequence[101];

int padovan(const int &n)
{
    if(n <= 3) return 1;
    else if(n <= 5) return 2;
    else if(sequence[n] == 0){
        sequence[n] = padovan(n-1) + padovan(n-5);
    }
    return sequence[n];
}

int main()
{
    int T, N;
    cin >> T;
    for(int t = 0; t < T; ++t){
        cin >> N;
        cout << padovan(N) << '\n';
    }
}<file_sep>/2292.cpp
#include <stdio.h>

int main(){
    int N, count = 0;
    scanf("%d", &N);
    if(N == 1) count = 0;
    else{
        while(1 + count*(count + 1) * 3 < N){
            ++count;
        }
    }
    printf("%d", count + 1);
}
<file_sep>/1874.cpp
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, cnt = 0;
    cin >> n;

    stack<int> s;
    vector<char> v;
    int arr[n];
    for(int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
    for(int i = 1; i <= n; ++i)
    {
        s.push(i);
        v.push_back('+');
        while(!s.empty() && s.top() == arr[cnt])
        {
            s.pop();
            v.push_back('-');
            ++cnt;
        }
    }
    if(!s.empty()) cout << "NO";
    else
    {
        int length = v.size();
        for(int i = 0; i < length; ++i)
        {
            cout << v[i] << '\n';
        } 
    }
    return 0;
}<file_sep>/1010.cpp
#include <stdio.h>

using namespace std;
int dp[30][30];

int C(const int &n, const int &k)
{
    if(n == k) return 1;
    if(k == 0) return 1;
    if(dp[n][k] != 0) return dp[n][k];
    else
    {
        dp[n][k] = C(n-1, k-1) + C(n-1, k);
        return dp[n][k];
    }
}

int main()
{
    int T, N, M;
    scanf("%d", &T);
    for(int t = 0; t < T; ++t)
    {
        scanf("%d %d", &N, &M);
        printf("%d\n", C(M, N));
    }
    return 0;
}<file_sep>/2941.cpp
#include <stdio.h>
#include <string.h>

int main(){
    char input[101];
    int num = 0;
    scanf("%s", input);
    int length = strlen(input);
    int i = 0;
    while(i < length){
        if(input[i] == 'c' && (input[i+1] == '=' || input[i+1] == '-')){
            i += 2;
            ++num;
        }
        else if(input[i] == 'd' && input[i+1] == 'z' && input[i+2] == '='){
            i += 3;
            ++num;
        }
        else if(input[i] == 'd' && input[i+1] == '-'){
            i += 2;
            ++num;
        }
        else if((input[i] == 'l' || input[i] == 'n')  && input[i+1] == 'j'){
            i += 2;
            ++num;
        }
        else if((input[i] == 's' || input[i] == 'z') && input[i+1] == '='){
            i += 2;
            ++num;
        }
        else{
            ++i;
            ++num;
        }
    }
    printf("%d", num);
}<file_sep>/1655.cpp
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, temp, first, second;
    cin >> N;
    priority_queue<int> pq_left;
    priority_queue<int, vector<int>, greater<int>> pq_right;

    cin >> first >> second;

    if(first < second){
        pq_left.push(first);
        pq_right.push(second);
    }

    else{
        pq_left.push(second);
        pq_right.push(first);
    }

    cout << first << '\n';
    cout << pq_left.top() << '\n';

    for(int n = 0; n < N - 2; ++n)
    {
        cin >> temp;
        if(pq_left.size() == pq_right.size())
        {
            if(pq_right.top() < temp)
            {
                pq_right.push(temp);
                pq_left.push(pq_right.top());
                pq_right.pop();
            }
            else pq_left.push(temp);
        }

        else if(pq_left.size() > pq_right.size())
        {
            if(temp < pq_left.top())
            {
                pq_left.push(temp);
                pq_right.push(pq_left.top());
                pq_left.pop();
            }
            else pq_right.push(temp);
        }
        /*
        else
        {
            if(pq_right.top() < temp)
            {
                pq_right.push(temp);
                pq_left.push(pq_right.top());
                pq_right.pop();
            }
            else pq_left.push(temp);
        }
        */
        cout << pq_left.top() << '\n';
    }
    
    return 0;
}

/*
1. pq_left.size() != pq_right.size();
    1) pq_left.size() > pq_right.size();
        (1) temp < pq_left.top()
            pq_left.push(temp)
            pq_right.push(pq_left.top())
            pq_left.pop();
        (2) pq_left.top() < temp < pq_right.top()
            pq_rifht.push(temp);
        (3) pq_right.top() < temp
            pq_right.push(temp)
    2) pq_right_size() > pq_left.size();
        (1) temp < pq_left.top()
            pq_left.push(temp);
        (2) pq_left.top() < temp < pq_right.top()
            pq_left.push(temp);
        (3) pq_right.top() < temp
            pq_right.push(temp);
            pq_left.push(pq_rignt.top());
            pq_right.pop();
2. pq_right.size() = pq_left.size()
    1) temp < pq_left.top()
        pq_left.push(temp)
    2) pq_left.top() < temp < pq_right.top()
        pq_left.push(temp)
    3) pq_right.top() < temp
        pq_right.push(temp)
        pq_left.push(pq_right.top())
        pq_right.pop()    
 */ <file_sep>/11057.cpp
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    int mod = 10007, ans = 0;
    int dp[1001][10] = {0};
    for(int i = 1; i <= N; ++i)
    {
        for(int j = 0; j < 10; ++j)
        {
            if(i == 1) dp[i][j] = 1;
            else
            {
                for(int k = 9; k >= j; --k)
                {
                    dp[i][j] += dp[i-1][k] % mod; 
                }
            }
        }
    }
    for(int i = 0; i < 10; ++i)
    {
        ans += dp[N][i] % mod;
    }
    cout << ans % mod;
    return 0;
}<file_sep>/2565.cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(vector<int> &a, vector<int> &b)
{
    return a[0] < b[0];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, len = 0;
    cin >> n;

    vector<vector<int>> v(n, vector<int>(2));
    int dp[n];

    for(int i = 0; i < n; ++i)
    {
        cin >> v[i][0] >> v[i][1];
    }
    sort(v.begin(), v.end(), compare);

    for(int i = 0; i < n; ++i)
    {
        dp[i] = 1;
        for(int j = 0; j < i; ++j)
        {
            if(v[i][1] > v[j][1])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        len = max(len, dp[i]);
    }
    cout << n - len;   

    return 0;
}<file_sep>/4963.cpp
#include <iostream>
#include <stack>
#include <string.h>

using namespace std;
#define MAX_SIZE 50
int w, h;
int num_island = 0;
int arr[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
int idx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int idy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

bool in_map(int row, int column)
{
    return (0 <= row && row < h && 0 <= column && column < w);
}

void DFS(int r, int c)
{
    stack<pair<int, int>> s;
    s.push({r, c});
    visited[r][c] = true;
    ++num_island;
    while(!s.empty())
    {
        int p_row = s.top().first;
        int p_col = s.top().second;
        s.pop();
        for(int i = 0; i < 8; ++i)
        {
            int c_row = p_row + idx[i];
            int c_col = p_col + idy[i];
            if(in_map(c_row, c_col) &&
                arr[c_row][c_col] == 1 &&
                !visited[c_row][c_col])
            {
                s.push({c_row, c_col});
                visited[c_row][c_col] = true;
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    while(1)
    {
        cin >> w >> h;
        if(w == 0 && h == 0) break;
        for(int row = 0; row < h; ++row)
        {
            for(int column = 0; column < w; ++column)
            {
                cin >> arr[row][column];
            }
        }

        for(int row = 0; row < h; ++row)
        {
            for(int column = 0; column < w; ++column)
            {
                if(!visited[row][column] && arr[row][column] == 1)
                {
                    DFS(row, column);
                }
            }
        }
        cout << num_island << endl;

        memset(arr, 0, sizeof(arr));
        memset(visited, false, sizeof(visited));
        num_island = 0;
    }
}<file_sep>/1931.cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(pair<int,int> a, pair<int,int> b)
{
    return a.second < b.second;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, ans = 1;
    cin >> N;
    vector<pair<int, int>> v(N);
    for(int n = 0; n < N; ++n)
    {
        cin >> v[n].first >> v[n].second;
    }
    sort(v.begin(), v.end(), compare);

    int s_time = v[0].first, e_time = v[0].second;
    for(int n = 1; n < N; ++n)
    {
        if(e_time <= v[n].first)
        {
            s_time = v[n].first;
            e_time = v[n].second;
            ++ans;
        }
    }
    cout << ans;
    return 0;
}<file_sep>/1789.cpp
#include <stdio.h>

using namespace std;

int main()
{
    long long S, n = 0;
    scanf("%d", &S);
    while(!(n * (n + 1) <= 2 * S && 2 * S < (n + 1) * (n + 2)))
    {
        ++n;
    }
    printf("%d", n);
    return 0;
}<file_sep>/17225.cpp
#include <iostream>
#include <queue>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int A, B, N;
    cin >> A >> B >> N;
    int t, m;
    char c;
    priority_queue<int> pq_Sangmin, pq_Jisu;
    for(int n = 0; n < N; ++n){
        cin >> t >> c >> m;
        if(c == 'B'){
            for(int i = 1; i <= m; ++i){
                if(!pq_Sangmin.empty() && t >= pq_Sangmin.top()){
                    t += A;
                    pq_Sangmin.push(t);
                }
                else if(pq_Sangmin.empty()){
                    t += A;
                    pq_Sangmin.push(t);
                }
                else{
                    t = pq_Sangmin.top() + A;
                    pq_Sangmin.push(t);
                }
            }
        }
        else if(c == 'R'){
            for(int i = 1; i <= m; ++i){
                if(!pq_Jisu.empty() && t >= pq_Jisu.top()){
                    t += B;
                    pq_Jisu.push(t);
                }
                else if(pq_Jisu.empty()){
                    t += B;
                    pq_Jisu.push(t);
                }
                else{
                    t = pq_Jisu.top() + B;
                    pq_Jisu.push(t);
                }
            }
        }
    }

    int count = pq_Sangmin.size() + pq_Jisu.size();
    priority_queue<int, vector<int>, greater<int>> Sangmin, Jisu;
    while(!pq_Sangmin.empty() && !pq_Jisu.empty()){
        if(pq_Sangmin.top() - A > pq_Jisu.top() - B){
            Sangmin.push(count--);
            pq_Sangmin.pop();
        }
        else{
            Jisu.push(count--);
            pq_Jisu.pop();
        }
    }

    while(!pq_Sangmin.empty()){
        Sangmin.push(count--);
        pq_Sangmin.pop();
    }

    while(!pq_Jisu.empty()){
        Jisu.push(count--);
        pq_Jisu.pop();
    }

    int s = Sangmin.size(), j = Jisu.size();
    cout << s << '\n';
    for(int a = 0; a < s - 1; ++a){
        cout << Sangmin.top() << " ";
        Sangmin.pop();
    }
    cout << Sangmin.top() << '\n';
    cout << j << '\n';
        for(int b = 0; b < j - 1; ++b){
        cout << Jisu.top() << " ";
        Jisu.pop();
    }
    cout << Jisu.top();
}<file_sep>/1012.cpp
#include <iostream>
#include <queue>

using namespace std;

int idx[4] = {-1, 1, 0, 0};
int idy[4] = {0, 0, -1, 1};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T, M, N, K;
    cin >> T;
    for(int t = 0; t < T; ++t)
    {
        cin >> M >> N >> K;
        int arr[M][N];
        bool visited[M][N];
        for(int p = 0; p < M; ++p){
            for(int q = 0; q < N; ++q)
            {
                arr[p][q] = 0;
                visited[p][q] = false;
            }
        }
        
        int x, y, count = 0;
        for(int k = 0; k < K; ++k)
        {
            cin >> x >> y;
            arr[x][y] = 1;
        }

        for(int a = 0; a < M; ++a){
            for(int b = 0; b < N; ++b)
            {
                if(!visited[a][b] && arr[a][b] == 1)
                {
                    queue<pair<int, int>> queue;
                    queue.push({a, b});
                    visited[a][b] = true;
                    ++count;
                    while(!queue.empty())
                    {
                        pair<int, int> parent = queue.front();
                        queue.pop();
                        int p_row = parent.first;
                        int p_column = parent.second;
                        for(int i = 0; i < 4; ++i)
                        {
                            int c_row = p_row + idx[i];
                            int c_column = p_column + idy[i];

                            if(!visited[c_row][c_column] &&
                                0 <= c_row && c_row < M &&
                                0 <= c_column && c_column < N &&
                                arr[c_row][c_column] == 1)
                            {
                                queue.push({c_row, c_column});
                                visited[c_row][c_column] = true;
                            }
                        }
                    }
                }
            }
        }
        cout << count << '\n';
    }
}<file_sep>/2164.cpp
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int N;
    cin >> N;
    queue<int> deck;

    for(int i = 1; i <= N; ++i)
    {
        deck.push(i);
    }

    while(deck.size() != 1)
    {
        deck.pop();
        deck.push(deck.front());
        deck.pop();
    }

    cout << deck.front();
    return 0;
}<file_sep>/1149.cpp
#include <iostream>

using namespace std;
int color[1000][3];
int dp[1000][3];

int min(const int &a, const int &b){
    return a > b ? b : a;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, R, G, B;
    cin >> N;
    for(int n = 0; n < N; ++n){
        cin >> color[n][0] >> color[n][1] >> color[n][2];
    }

    dp[0][0] = color[0][0];
    dp[0][1] = color[0][1];
    dp[0][2] = color[0][2];

    for(int n = 1; n < N; ++n){
        dp[n][0] = color[n][0] + min(dp[n-1][1], dp[n-1][2]);
        dp[n][1] = color[n][1] + min(dp[n-1][0], dp[n-1][2]);
        dp[n][2] = color[n][2] + min(dp[n-1][0], dp[n-1][1]);
    }

    cout << min(dp[N-1][0], min(dp[N-1][1], dp[N-1][2]));
}
<file_sep>/15577.cpp
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    double N, temp, first, second;
    cin >> N;
    priority_queue<double, vector<double>, greater<double>> pq;
    for(int i = 0; i < N; ++i)
    {
        cin >> temp;
        pq.push(temp);
    }
    while(N > 1)
    {
        first = pq.top();
        pq.pop();
        second = pq.top();
        pq.pop();
        pq.push((first + second)/2);
        N--;
    }
    cout << fixed;
    cout.precision(6);
    cout << pq.top();
}<file_sep>/11051.cpp
#include <iostream>

int p = 10007;
int dp[1001][1001];

using namespace std;

int C(int N, int K) {
    if(dp[N][K] != 0) return dp[N][K];
    if(N == K || K == 0) {
        dp[N][K] = 1;
        return 1;
    }
    dp[N][K] = (C(N-1, K) + C(N-1, K-1)) % p; 
    return dp[N][K];
}

int main() {
    int N, K;
    cin >> N >> K;
    cout << C(N, K) << endl;
}<file_sep>/2675.cpp
#include <stdio.h>
#include <string.h>

int main(){
    int T, R;
    char S[20];
    scanf("%d", &T);
    
    for(int i = 0; i < T; ++i){
        scanf("%d %s", &R, S);
        
        for(int j = 0; j <strlen(S); ++j){
            
            for(int k = 0; k < R; ++k){
                printf("%c", S[j]);
            }
        }
        printf("\n");
    }
}
<file_sep>/16395.cpp
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    int C[n][k];
    
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < k; ++j)
        {
            if(i == j || j == 0) C[i][j] = 1;
            else
            {
                C[i][j] = C[i-1][j] + C[i-1][j-1];
            }
        }
    }
    cout << C[n-1][k-1];
    return 0;
}<file_sep>/19638.cpp
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, H, T, count = 0;
    cin >> N  >> H >> T;

    priority_queue<int> pq;

    for(int i = 0; i < N; ++i)
    {
        int giant_Height;
        cin >> giant_Height;
        pq.push(giant_Height);
    }
    
    for(int i = 0; i < T; ++i)
    {
        int tallest = pq.top();
        if(tallest < H)
        {
            break;
        }

        if(tallest > 1)
        {
            ++count;
            pq.pop();
            pq.push(tallest / 2);
        }
    }

    if(pq.top() < H)
    {
        cout << "YES\n" << count << "\n";
    }
    else
    {
        cout << "NO\n" << pq.top() << "\n";
    }
}<file_sep>/2468.cpp
#include <iostream>
#include <string.h>

using namespace std;

int arr[100][100];
int N;
bool visited[100][100];

int idx[4] = {0, 0, -1, 1};
int idy[4] = {-1, 1, 0, 0};

void DFS(int i, int j, int h)
{
    visited[i][j] = true;
    for(int k = 0; k < 4; ++k){
        int r = i + idx[k];
        int c = j + idy[k];
        if(!visited[r][c] &&
            0 <= r && r < N &&
            0 <= c && c < N &&
            arr[r][c] > h)
            DFS(r, c, h);
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int max_height = 0, ans = 0;
    cin >> N;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            cin >> arr[i][j];
            max_height = max(max_height, arr[i][j]);
        }
    }
    for(int h = 0; h < max_height; ++h){
        memset(visited, false, sizeof(visited));
        int cnt = 0;
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++j){
                if(!visited[i][j] && arr[i][j] > h){
                    DFS(i, j, h);
                    ++cnt;
                }   
            }
        }
       
        ans = max(ans, cnt);
    }
    cout << ans;
}<file_sep>/1463.cpp
#include <iostream>
#include <algorithm>

using namespace std;

int goUp(int n){
    if(n <= 1) return 0;
    else{
        return min(n % 3 + goUp(n/3) + 1, n % 2 + goUp(n/2) + 1);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    cout << goUp(N);
    return 0;
}<file_sep>/1427_1.cpp
#include <stdio.h>
#include <string.h>

void merge(int *arr, int *sorted, int start, int middle, int end){
    int l = start, r = middle + 1, i = start;
    while(l <= middle && r <= end){
        if(arr[l] < arr[r]){
            sorted[i] = arr[r];
            ++r;
        }
        else{
            sorted[i] = arr[l];
            ++l;
        }
        ++i;
    }

    if(l > middle){
        while(r <= end){
            sorted[i] = arr[r];
            ++r;
            ++i;
        }
    }
    else{
        while(l <= middle){
            sorted[i] = arr[l];
            ++l;
            ++i;
        }
    }

    for(int k = start; k <= end; ++k){
        arr[k] = sorted[k];
    }
}

void merge_sort(int *arr, int *sorted, int start, int end){
    if(start < end){
        int middle = (start + end) / 2;
        merge_sort(arr, sorted, start, middle);
        merge_sort(arr, sorted, middle + 1, end);
        merge(arr, sorted, start, middle, end);
    }
}

int main(){
    char arr[10];
    int ans[10];
    int sorted[10] = {0};

    scanf("%s", arr);
    int len = strlen(arr);
    for(int i = 0; i < len; ++i){
        ans[i] = (int)arr[i] - 48;
    }
    
    merge_sort(ans, sorted, 0, len - 1);

    for(int i = 0; i < len; ++i){
        printf("%d",ans[i]);
    }
}<file_sep>/4949.cpp
#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool check_balance(const string &str)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    stack<char> s;
    int length = str.length();
    for(int i = 0; i < length; ++i)
    {
        if(str[i] == '(')
        {
            s.push('(');
        }
        else if(str[i] == '[')
        {
            s.push('[');
        }
        else if(str[i] == ')')
        {
            if(!s.empty() && s.top() == '(') s.pop();
            else return false;
        }
        else if(str[i] == ']')
        {
            if(!s.empty() && s.top() =='[') s.pop();
            else return false;
        }
    }
    return s.empty();
}
int main()
{
    while(1)
    {
        string str;
        getline(cin, str);
        if(str[0] == '.') break;
        if(check_balance(str)) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}<file_sep>/11074.cpp
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, K, ans = 0;
    cin >> N >> K;
    int A[N];
    for(int n = 0; n < N; ++n)
    {
        cin >> A[n];
    }
    for(int i = N-1; i >= 0; --i)
    {
        if(A[i] <= K)
        {
            ans += K / A[i];
            K = K - (K / A[i]) * A[i];
        }
    }
    cout << ans;
    return 0;
}<file_sep>/2231.cpp
#include <stdio.h>

int dividesum(int &input){
    int arr[7] = {0}, temp = input, i = 0, result = input;
    while(temp > 0){
        arr[i] = temp % 10;
        ++i;
        temp /= 10;
    }
    for(int i = 0; i < 7; ++i){
        result += arr[i];
    }
    return result;
}

int main(){
    int N;
    scanf("%d", &N);
    int length = 0, temp = N;
    bool check = true;
    while(temp > 0){
        temp /= 10;
        ++length;
    }
    int start = N - length * 10;
    for(int i = start; i < N; ++i){
        if(dividesum(i) == N){
            printf("%d", i);
            check = false;
            break;
        }
    }
    if(check) printf("%d", 0);
}<file_sep>/1699.cpp
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    int dp[100001] = {0};
    for(int i = 1; i <= N; ++i){
        dp[i] = i;
        for(int j = 1; j * j <= i; ++j)
        {
            dp[i] = min(dp[i], dp[i-j*j] + 1);
        }
    }
    cout << dp[N];
    return 0;
}<file_sep>/9012.cpp
#include <iostream>
#include <string>
#include <stack>

using namespace std;

bool check_VPS(const string input)
{
    int length = input.length();
    stack<char> s;

    for(int i = 0; i < length; ++i)
    {
        if(input[i] == '(')
        {
            s.push('(');
        }

        else if(input[i] == ')')
        {
            if(s.empty()) return false;
            else s.pop();
        }
    }
    return s.empty();
}

int main()
{
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    while(T--)
    {
        string input;
        cin >> input;
        if(check_VPS(input)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    
    return 0;
}<file_sep>/10814.cpp
#include <iostream>
#include <string>
#include <algorithm>


using namespace std;

class Person{
private:
    string name;
    int age;
    int order;
public:
    Person(const string &name_input = "Noname", const int &age_input = 0, const int &order_input = 0)
        : name(name_input)
        , age(age_input)
        , order(order_input)
    {}

    void setPersonInfo(int age_input, string name_input, int order_input)
    {
        name = name_input;
        age = age_input;
        order = order_input;
    }

    int getage(){
        return age;
    }

    int getorder(){
        return order;
    }

    string getname(){
        return name;
    }
};

bool compare(Person A, Person B){
    if(A.getage() == B.getage()) return A.getorder() < B.getorder();
    else return A.getage() < B.getage();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, age;
    string name;
    cin >> N;
    Person member[N];
    for(int i = 0; i < N; ++i){
        cin >> age >> name;
        member[i].setPersonInfo(age, name, i);
    }

    sort(member, member + N , compare);

    for(int i = 0; i < N; ++i){
        cout << member[i].getage() << ' ' << member[i].getname() << '\n';
    }
}<file_sep>/11650.cpp
#include <stdio.h>
#include <algorithm>
#include <vector>

class Point
{
public:
    int x;
    int y;

    Point(const int &x_input, const int &y_input)
    {
        x = x_input;
        y = y_input;
    }
};

bool compare(Point &a, Point &b){
    if(a.x == b.x) return a.y < b.y;
    else  return a.x < b.x;
}

int main(){
    int N;
    scanf("%d", &N);
    std::vector<Point> p;
    int x, y;
    for(int i = 0; i < N; ++i){
        scanf("%d %d", &x, &y);
        p.push_back(Point(x,y));
    }
    sort(p.begin(), p.end(), compare);
    for(int i = 0; i < N; ++i){
        printf("%d %d\n", p[i].x, p[i].y);
    }
}<file_sep>/1202.cpp
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, K, m, v, c;
    long long ans = 0;
    cin >> N >> K;
    priority_queue<pair<int, int>> jewerlly;
    multiset<int> bag;
    for(int n = 0; n < N; ++n)
    {
        cin >> m >> v;
        jewerlly.push({v, m});
    }

    for(int k = 0; k < K; ++k)
    {
        cin >> c;
        bag.insert(c);
    }

    while(!bag.empty() && !jewerlly.empty())
    {
        multiset<int>::iterator iter = bag.lower_bound(jewerlly.top().second);
        
        if(iter != bag.end())
        {
            bag.erase(iter);
            ans += jewerlly.top().first;
            jewerlly.pop();
        }
        else jewerlly.pop();
    }
    cout << ans;
}<file_sep>/2798.cpp
#include <stdio.h>

int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    int arr[100], sum = 0, max = 0;
    for(int i = 0; i < N; ++i){
        scanf("%d", &arr[i]);
    }
    for(int i = 0; i < N; ++i){
        for(int j = i + 1; j < N; ++j){
            for(int k = j + 1; k < N; ++k){
                sum = arr[i] + arr[j]+ arr[k];
                if(sum <= M && max < sum){
                    max = sum;
                }
            }
        }
    }
    printf("%d", max);
}<file_sep>/11651.cpp
#include <stdio.h>
#include <algorithm>
#include <vector>

class Point{
private:
    int x;
    int y;
public:
    Point(const int &x_input, const int &y_input){
        x = x_input;
        y = y_input;
    }

    const int getx(){
        int a = x;
        return a;
    }

    const int gety(){
        int b = y;
        return b;
    }
};

bool compare(Point &a, Point &b){
    if(a.gety() == b.gety()) return a.getx() < b.getx();
    else return a.gety() < b.gety();
}

int main(){
    int N;
    scanf("%d", &N);
    int x = 0, y = 0;
    std::vector<Point> p;
    for(int i = 0; i < N; ++i){
        scanf("%d %d", &x, &y);
        p.push_back(Point(x,y));
    }
    sort(p.begin(), p.end(), compare);
    for(int i = 0; i < N; ++i){
        printf("%d %d\n", p[i].getx(), p[i].gety());
    }
}<file_sep>/1427_3.cpp
#include <stdio.h>
#include <algorithm>
#include <string.h>

bool compare(char a, char b){
    return a > b;
}

int main(){
    char arr[11];
    scanf("%s", arr);
    std::sort(arr, arr + strlen(arr), compare);
    printf("%s", arr);
}<file_sep>/15903.cpp
#include <iostream>
#include <queue>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long n, m, temp;
    long long ans = 0;
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        cin >> temp;
        pq.push(temp);
    }
    while(m--){
        long long first = pq.top();
        pq.pop();
        long long second = pq.top();
        pq.pop();
        pq.push(first + second);
        pq.push(first + second);
    }
    while(!pq.empty()){
        ans += pq.top();
        pq.pop();
    }
    cout << ans;
}<file_sep>/10809.cpp
#include <stdio.h>
#include <string.h>
int main(){
    char input[101];
    char alphabet[26];
    scanf("%s", input);
    int length = strlen(input);
    for(char i = 'A'; i <= 'Z' ; ++i){
        alphabet[i - 'A'] = -1;
        for(int j = 0; j < length; ++j){
            if('a' <= input[j]){
                input[j] -= 32;
            }
            if(input[j] == i){
                alphabet[i - 'A'] = j;
                break;
            }
        }
    }
    for(int i = 0; i < 26; ++i){
        printf("%d ", alphabet[i]);
    }
    
}<file_sep>/2750.cpp
#include <stdio.h>

int main(){
    int N;
    scanf("%d", &N);
    int arr[N];
    for(int i =0; i < N; ++i){
        scanf("%d", &arr[i]);
    }

    for(int i = 1; i < N; ++i){
        int key = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j]> key){
            arr[j+1] = arr[j];
            j = j - 1;
        }
        arr[j+1] = key;
    }
   
    for(int i = 0; i < N; ++i){
        printf("%d ", arr[i]);
    }
}<file_sep>/10845.cpp
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Queue
{
private:
    vector<int> m_v;
public:

    void push(const int &input)
    {
        m_v.push_back(input);
    }

    int pop()
    {
        if(empty()) return -1;
        else
        {
            int temp;
            temp =  m_v.front();
            m_v.erase(m_v.begin());
            return temp;
        } 
    }

    int size()
    {
        return m_v.size();
    }

    int empty()
    {
        if(m_v.empty()) return 1;
        else return 0;
    }

    int front()
    {
        if(m_v.empty()) return -1;
        else return m_v.front();
    }

    int back()
    {
        if(m_v.empty()) return -1;
        else return m_v.back();
    }

    void order(string s_in)
    {
        if(s_in == "push")
        {
            int temp;
            cin >> temp;
            push(temp);
        }
        else if(s_in == "pop")
        {
            cout << pop() << '\n';
        }
        else if(s_in == "size")
        {
            cout << size() << '\n';
        }
        else if(s_in == "empty")
        {
            cout << empty() << '\n';
        }
        else if(s_in == "front")
        {
            cout << front() << '\n';
        }
        else if(s_in == "back")
        {
            cout << back() << '\n';
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    string s_in;
    cin >> N;

    Queue q;

    for(int i = 0; i < N; ++i)
    {
        cin >> s_in;
        q.order(s_in);
    }
    return 0;
}<file_sep>/1966.cpp
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(const int i, const int j)
{
    return i > j;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;

    for(int i = 0; i < T; ++i)
    {
        int N, M, count = 0;
        cin >> N >> M;
        queue<int> q;
        queue<int> letter;
        vector<int> v;
        for(int j = 0; j < N; ++j)
        {
            int temp;
            cin >> temp;
            v.push_back(temp);
            q.push(temp);
            letter.push(j);
        }
        sort(v.begin(),v.end(), compare);
        while(!q.empty())
        {
            if(v.front() == q.front())
            {
                ++count;
                if(letter.front() == M)
                {
                    cout << count << '\n';
                    break;
                }
                v.erase(v.begin());
                q.pop();
                letter.pop();
            }
            else{
                q.push(q.front());
                q.pop();
                letter.push(letter.front());
                letter.pop();
            }
        }
    }
    return 0;
}<file_sep>/10828.cpp
#include <iostream>
#include <string>

using namespace std;

class Stack
{
private:
    int *m_arr;
    int m_top;
    int m_size;

public:
    Stack(const int& max_size)
    {
        m_arr = new int[max_size];
        m_top = -1;
        m_size = 0;
    }

    ~Stack()
    {
        delete [] m_arr;
    }

    void push(const int &input)
    {
        m_arr[m_size] = input;
        ++m_size;
        ++m_top;
    }

    void pop()
    {
        if(empty()) cout << -1 << endl;
        else
        {
            cout << m_arr[m_size - 1] << endl;
            --m_size;
            --m_top;
        }
    }

    void top()
    {
        if(empty()) cout << -1 << endl;
        else cout << m_arr[m_size - 1] << endl;
    }

    int empty()
    {
        if(m_top < 0) return 1;
        else return 0;
    }

    void size()
    {
        cout << m_size << endl;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    Stack stack(10000);
    string str_in;
    int push_in;
    for(int i = 0; i < N; ++i)
    {
        cin >> str_in;
        if(str_in == "push")
        {
            cin >> push_in;
            stack.push(push_in);
        }
        else if(str_in == "top") stack.top();
        else if(str_in == "size") stack.size();
        else if(str_in == "empty")
        { 
            if(stack.empty() == 1) cout << 1 << endl;
            else cout << 0 << endl;
        }
        else if(str_in == "pop") stack.pop();
    }
}<file_sep>/1946.cpp
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    int ans[T];
    for(int t = 0; t < T; ++t)
    {
        int N;
        cin >> N;
        vector<int> v(N+1);
        int document, interview;
        for(int n = 0; n < N; ++n)
        {
            cin >> document >> interview;
            v[document] = interview;
        }

        int member = 1, current_ranking = v[1];
        for(int i = 2; i <= N; ++i)
        {
            if(v[i] < current_ranking)
            {
                current_ranking = v[i];
                ++member;
            }
        }
        cout << member << '\n';
    }

    return 0;
}<file_sep>/11720.cpp
#include <stdio.h>

int main(){
    int N, sum = 0;
    char arr[100];
    scanf("%d %s", &N, arr);
    for(int i = 0; i < N; ++i){
        sum += (int)arr[i] - 48;
    }
    printf("%d", sum);
}<file_sep>/1157.cpp
#include <stdio.h>
#include <string.h>
int main(){
    char a[1000001];
    int alphabet[26] = {0};
    scanf("%s", a);
    int length = strlen(a);
    for(int i = 0; i < length; ++i){// 알파벳 대문자로 바꾸기
        if('a' <= a[i]) a[i] = a[i] - 32;
            ++alphabet[a[i] - 'A'];
    }

    int max = 0, max_num = 0, position = 0;
    for(int i = 0; i < 26; ++i){
        if(max < alphabet[i]) max = alphabet[i];
    }

    for(int i = 0; i < 26; ++i){
        if(max == alphabet[i]){
            ++max_num;
            position = i;
        } 
    }

    printf("%c",(max_num > 1)? '?' : 'A' + position);
}<file_sep>/1260.cpp
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

void BFS(int parent, vector<int> adj[], bool visited[])
{
    queue<int> queue;
    queue.push(parent);
    while(!queue.empty())
    {
        parent = queue.front();
        queue.pop();

        if(!visited[parent])
        {
            visited[parent] = true;
            cout << parent << " ";
        }
        for(int i = 0; i < adj[parent].size(); ++i)
        {
            int child = adj[parent][i];
            if(!visited[child])
            {
                queue.push(child);
            }
        }
    }
}

void DFS(int parent, vector<int> adj[], bool visited[])
{
    visited[parent] = true;
    cout << parent << " ";
    for(int i = 0; i < adj[parent].size(); ++i)
    {
        int child = adj[parent][i];
        if(!visited[child])
        {
            DFS(child, adj, visited);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M, V, v, w;

    cin >> N >> M >> V;
    
    vector<int> adj[1001];
    bool visited[1001];
    bool visited2[1001];

    for(int m = 0; m < M; ++m)
    {
        cin >> v >> w;
        adj[v].push_back(w);
        adj[w].push_back(v);
    }

    for(int i = 1; i <= N; ++i)
    {
        sort(adj[i].begin(), adj[i].end());
    }

    DFS(V, adj, visited);
    cout << '\n';
    BFS(V, adj, visited2);
}<file_sep>/2293.cpp
#include <stdio.h>

using namespace std;

int main()
{
    int n, k;
    int input[100];
    int dp[10001] = {0};

    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; ++i) scanf("%d", &input[i]);
        
    dp[0] = 1;

    for(int i = 0; i < n; ++i)
    {
        for(int j = 1; j <= k; ++j)
        {
            if(input[i] <= j)
            {
                dp[j] += dp[j - input[i]];
            }
        }
    }
    printf("%d", dp[k]);
    return 0;
}<file_sep>/1697.cpp
#include <iostream>
#include <queue>

using namespace std;

bool visited[100001] = {false,};

void BFS(int subin, int sister)
{
    queue<pair<int, int>> graph;
    graph.push({subin, 0});
    visited[subin] = true;
    if(graph.front().first == sister)
    {
        cout << graph.front().second;
        return;   
    }
    while(!graph.empty())
    {
        pair<int, int> x = graph.front();
        graph.pop();
        if(x.first-1 == sister || x.first+1 == sister || 2*x.first == sister)
        {
            cout << x.second + 1;
            return;
        }
        if(0< x.first && x.first - 1<= 100000 && !visited[x.first-1])
        {
            graph.push({x.first-1, x.second + 1});
            visited[x.first-1] = true;
        } 
        if(x.first + 1 <= 100000 && !visited[x.first+1])
        {
            graph.push({x.first+1, x.second + 1});
            visited[x.first+1] = true;
        } 
        if(2*x.first <= 100000 && !visited[2*x.first])
        {
            graph.push({2*x.first, x.second + 1});
            visited[2*x.first] = true;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin >> N >> K;
    BFS(N, K);
}<file_sep>/2667.cpp
#include <stdio.h>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;
int N, temp;
int arr[25][25];
bool visited[25][25];
vector<int> ans;

int idx[4] = {-1, 1, 0, 0};
int idy[4] = {0, 0, -1, 1};

bool inSquare(int row, int column)
{
    if(0 <= row && row < N && 0 <= column && column < N)
    {
        return true;
    }
    else return false;
}

void dfs(int row, int column)
{
    if(arr[row][column] == 1 && visited[row][column] == false)
    {
        int count = 0;
        stack<pair<int, int>> stack;
        stack.push({row, column});
        while(!stack.empty())
        {
            row = stack.top().first;
            column = stack.top().second;
            stack.pop();
            
            if(!visited[row][column])
            {
                visited[row][column] = true;
                ++count;
            }

            for(int i = 0; i < 4; ++i)
            {
                int child_row = row + idx[i];
                int child_column = column + idy[i];
               
                if(inSquare(child_row, child_column) && arr[child_row][child_column] == 1)
                {
                    if(!visited[child_row][child_column])
                    {
                        stack.push({child_row, child_column});
                    }
                }
            }
        }
        ans.push_back(count);
        count = 0;
    }
}

int main()
{
    scanf("%d", &N);
    
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            scanf("%1d", &arr[i][j]);
        }
    }
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j)
        {
            dfs(i, j);
        }
    }
    
    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());
    
    for(int i = 0; i < ans.size(); ++i)
    {
        printf("%d\n", ans[i]);
    }
}<file_sep>/6603.cpp
#include <iostream>
#define MAX_SIZE 13

using namespace std;

int lotto[MAX_SIZE];
int memory[6];
int K;

void dfs(int start, int depth) {
    if(depth == 6) {
        for(int i = 0; i < 6; ++i) {
            cout << memory[i] << " ";
        }
        cout << endl;
        return;
    }

    for(int i = start; i < K; ++i) {
        memory[depth] = lotto[i];
        dfs(i + 1, depth + 1);
    }
}

int main()
{
    while(1) {
        cin >> K;
        if(K == 0) break;
        for(int k = 0; k < K; ++k) {
            cin >> lotto[k];
        }
        dfs(0, 0);
        cout << endl;
    }
    return 0;
}<file_sep>/1715.cpp
#include <iostream>

using namespace std;

class Heap
{
private:
    int heap[100001];
    int heap_count;
public:
    Heap() {
        heap_count = 0;
    }
    bool empty();
    int top();
    void pop();
    void push(const int &a);
    void heapify(int i);

};

bool Heap::empty()
{
    return heap_count == 0;
}

int Heap::top()
{
    return heap[0];
}

void Heap::pop()
{
    heap[0] = heap[--heap_count];
    heapify(0);
}

void Heap::push(const int &a)
{
    heap[heap_count++] = a;
    for(int i = heap_count - 1; i > 0;){
        int parent = (i - 1) >> 1;
        if(heap[parent] < heap[i]) break;
        swap(heap[parent], heap[i]);
        i = parent;
    }
}

void Heap::heapify(int i)
{
    int min = i;
    int left = 2*i + 1;
    int right = 2*(i + 1);
    if(left < heap_count && heap[min] > heap[left]){
        min = left;
    }
    if(right < heap_count && heap[min] > heap[right]){
        min = right;
    }
    if(min != i){
        swap(heap[min], heap[i]);
        heapify(min);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Heap H;
    int N, temp, ans = 0;
    cin >> N;
    for(int n = 0; n < N; ++n){
        cin >> temp;
        H.push(temp);
    }
    for(int n = 0; n < N - 1; ++n){
        int first = H.top();
        H.pop();
        int second = H.top();
        H.pop();
        ans += first + second;
        H.push(first + second);
    }
    cout << ans;
    return 0;
}<file_sep>/5430.cpp
#include <iostream>
#include <deque>
#include <string>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    for(int i = 0; i < T; ++i)
    {
        string p, input;
        int n;
        cin >> p >> n >> input;
        
        int length = input.length();
        deque<int> deq;
        string temp;

        for(int j = 0; j < length; ++j)
        {
            if('0' <= input[j] && input[j] <= '9')
            {
                temp += input[j];
            }
            else if(input[j] == ',' || input[j] == ']')
            {
                if(!temp.empty())
                {
                    deq.push_back(stoi(temp));
                    temp.clear();
                }
            }
        }

        int start = 0, end = n;
        bool reverse = false, error = false;

        for(int j = 0; j < p.length(); ++j)
        {
            if(p[j] == 'R')
            {
                reverse = !reverse;
            }
            else
            {
                if(deq.empty())
                {
                    error = true;
                    break;
                }
                else if(reverse)
                {
                    deq.pop_back();
                }
                else
                {
                    deq.pop_front();
                }
            }
        }
        if(error) cout << "error\n";
        else 
        {
            cout << '[';
            if(!reverse)
            {
                while(!deq.empty())
                {
                    cout << deq.front();
                    deq.pop_front();
                    if(!deq.empty())
                        cout << ',';
                }
            }
            else
            {
                while(!deq.empty())
                {
                    cout << deq.back();
                    deq.pop_back();
                    if(!deq.empty())
                        cout << ',';
                }

            }
            cout << "]\n";
        }
    }
    return 0;
}<file_sep>/15649.cpp
#include <iostream>

using namespace std;

int N, M;
bool visited[9]{0};
int arr[9]{0};

void backtrack(int cnt){
    if(cnt == M){
        for(int i = 0; i < M; ++i){
            cout << arr[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for(int i = 1; i <= N; ++i){
        if(!visited[i]){
            visited[i] = true;
            arr[cnt] = i;
            backtrack(cnt + 1);
            visited[i] = false;
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    int cnt = 0;
    backtrack(cnt);
}<file_sep>/14241.cpp
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, sum = 0, score = 0, first, second;
    cin >> N;
    cin >> first;
    for(int n = 0; n < N - 1; ++n)
    {
        cin >> second;
        score += first * second;
        first += second;
    }

    cout << score << endl;
}
<file_sep>/1021.cpp
#include <iostream>
#include <deque>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, count = 0, index = 0;;
	cin >> N >> M;

	deque<int> deq;

	for(int i = 1; i <= N; ++i)
	{
		deq.push_back(i);	
	}

	while(M--)
	{
		int temp;
		cin >> temp;

		for(int i = 0; i < deq.size(); ++i)
		{
			if(deq[i] == temp)
			{
				index = i;
				break;
			}
		}

		if(deq.size() - index > index)
		{
			while(deq.front() != temp)
			{
				deq.push_back(deq.front());
				deq.pop_front();
				++count;
			}
		}
		else
		{
			while(deq.front() != temp)
			{
				deq.push_front(deq.back());
				deq.pop_back();
				++count;
			}
		}
		deq.pop_front();
	}

	cout << count;
}<file_sep>/1912.cpp
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, seq, ans, input;
    cin >> n >> seq;
    ans = seq;
    for(int i = 1; i < n; ++i)
    {
        cin >> input;
        seq = seq < 0 ? input : seq + input;
        ans = ans > seq ? ans : seq;
    }
    cout << ans;
    return 0;
}<file_sep>/[try]6549.cpp
#include <iostream>
#include <vector>

using namespace std;

int print(const vector<int> &h, const int &n)
{
    int area = 0, height = 1000000001, width = 0;

    for(int i = 0; i < n; ++i)
    {
        if(h[i] < height)
        {
            height = h[i];
            ++width;
            if(area < h[i] * (width + 1))
            {
                area = height * width;
            }
        }
        else
        {
            if(area <= height * (width + 1))
            {
                ++width;
                area = height * width;
            }
            else
            {
                
            }
        } 
    }
    return area;
}


int main()
{
    int n = 0;
    while(true)
    {
        cin >> n;
        if(n == 0) break;
        vector<int> h(n);
        for(int i = 0; i < n; ++i)
        {
            cin >> h[i];
        }
        cout << '\n' << print(h,n);
    }
    return 0;
}<file_sep>/16953.cpp
#include <stdio.h>

using namespace std;

int main()
{
    int A, B, ans = 0;;
    scanf("%d %d", &A, &B);
    while(B > A)
    {
        if(B % 2 == 0){
            B /= 2;
            ++ans;
        }
        else if(B % 10 == 1){
            B /= 10;
            ++ans;
        }
        else{
            break;
        }
    }
    A == B ? printf("%d", ans + 1) : printf("%d", -1);

    return 0;
}<file_sep>/18870.cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    vector<int> v;
    int temp = 0;
    for(int i = 0; i < N; ++i){
        cin >> temp;
        v.push_back(temp);
    }

    vector<int> copy(v);

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());





    for(int i = 0; i < N; ++i){
        int ans = lower_bound(v.begin(), v.end(), copy[i]) - v.begin();

        cout << ans << ' ';
    }
}<file_sep>/11399.cpp
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N, ans = 0;
    scanf("%d", &N);
    vector<int> P(N);
    for(int i = 0; i < N; ++i)
    {
        scanf("%d", &P[i]);
    }
    sort(P.begin(), P.end());
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j <= i; ++j)
        {
            ans += P[j];
        }
    }
    printf("%d", ans);
    return 0;
}<file_sep>/2869.cpp
#include <stdio.h>

int main(){
    int A, B, V, day = 0;
    scanf("%d %d %d", &A, &B, &V);
    V -= A;
    if(V % ( A - B ) == 0){
        day = V / ( A - B ) + 1;
    }
    else{
        day = V / ( A - B ) + 2; 
    }
    printf("%d", day);
}

/* V - A + B
 *   ...
 * V - n(A - B) - A < 0 : day = n + 1
 * V - n(A - B) - A = 0 : day = n + 1
 */<file_sep>/[try]2261.cpp
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int distance(pair<int, int> a, pair<int, int> b)
{
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

bool compare(const pair<int, int> a, const pair<int, int> b)
{
    if(a.first < b.first) return a < b;
    else if(a.first > b.first) return a > b;
    else if(a.second < b.second) return a < b;
}

int main()
{
    int n;
    vector<pair<int, int>> v(n);

    for(int i = 0; i < n; ++i)
    {
        cin >> v[i].first >> v[i].second;
    }

    sort(v.begin(), v.end(), compare);
    

    return 0;
}<file_sep>/2225.cpp
#include <iostream>

using namespace std;

int dp[201][201];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, K, mod = 1000000000;
    cin >> N >> K;
    
    for(int k = 1; k <= K; ++k)
    {
        dp[0][k] = 1;
    }
    for(int n = 1; n <= N; ++n)
    {
        for(int k = 0; k <= K; ++k)
        {
            if(k == 0) dp[n][k] = 0;
            else if(k == 1) dp[n][k] = 1;
            else
            {
                dp[n][k] = (dp[n][k-1] + dp[n-1][k]) % mod;
            }
        }
    }
    cout << dp[N][K];
    return 0;
}


// dp[n][k] = dp[n][k-1] + dp[n-1][k-1] + dp[n-2][k-1] + dp[n-3][k-1] ... + dp[1][k-1] + dp[0][k-1];
// dp[n-1][k] = dp[n-1][k-1] + ... + dp[0][k-1];
// dp[k][n] = dp[k-1][n] + ... + d[k-1][0];<file_sep>/11866.cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

void josephus(const int &n, const int &k)
{

}

int main()
{
    int N, K, count = 1;
    cin >> N >> K;
    queue<int> q;
    vector<int> ans;

    for(int i = 1; i <= N; ++i)
    {
        q.push(i);
    }

    while(!q.empty())
    {
        if(count == K)
        {
            ans.push_back(q.front());
            q.pop();
            count = 1;
            
        }
        else
        {
            q.push(q.front());
            q.pop();
            ++count;
        }
    }

    cout << '<';
    for(int i = 0; i < N - 1; ++i)
    {
        cout << ans[i] << ", ";
    }
    cout << ans[N-1] << '>';

    return 0;
}<file_sep>/2775.cpp
#include <iostream>

int main(){
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    scanf("%d", &T);

    int arr[15][15];
    for(int i = 0; i < 15; ++i){
        arr[0][i] = i + 1;
        arr[i][0] = 1;
    }
    for(int i = 1; i < 15; ++i){
        for(int j = 1; j < 15; ++j){
            arr[i][j] = arr[i][j-1] + arr[i-1][j];  
        }
    }

    for(int i = 0; i < T; ++i){
        int k, n;
        scanf("%d %d", &k, &n);
        printf("%d\n",arr[k][n-1]);
    }
}
<file_sep>/11286.cpp
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, x;
    priority_queue<int, vector<int>, greater<int>> pq_pos, pq_neg;

    cin >> N;
    while(N--){
        cin >> x;
        if(x > 0) pq_pos.push(x);
        else if(x < 0) pq_neg.push(-x);
        else{
            if(pq_pos.empty() && pq_neg.empty()) cout << "0\n";
            else if(pq_pos.empty()){
                cout << -pq_neg.top() << '\n';
                pq_neg.pop();
            }
            else if(pq_neg.empty()){
                cout << pq_pos.top() << '\n';
                pq_pos.pop();
            }
            else{
                if(pq_pos.top() < pq_neg.top()){
                    cout << pq_pos.top() << '\n';
                    pq_pos.pop();
                }
                else{
                    cout << -pq_neg.top() << '\n';
                    pq_neg.pop();
                }
            }
        }
    }

    return 0;
}<file_sep>/1541.cpp
#include <stdio.h>

using namespace std;

int main()
{
    int sign = 1, number = 0, ans = 0;
    char oper;
    scanf("%d", &number);
    while(scanf("%c", &oper) != EOF)
    {
        ans = ans + number * sign;
        if(oper == '-') sign = -1;
        scanf("%d", &number);
    }
    printf("%d", ans);
    return 0;
}<file_sep>/18258.cpp
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    string s_in;
    cin >> N;

    queue<int> q;

    for(int i = 0; i < N; ++i)
    {
        cin >> s_in;
        if(s_in == "push")
        {
            int temp;
            cin >> temp;
            q.push(temp);
        }
        else if(s_in == "pop")
        {
            if(q.empty()) cout << -1 << '\n';
            else
            {
                cout << q.front() << '\n';
                q.pop();
            }
        }
        else if(s_in == "size")
        {
            cout << q.size() << '\n';
        }
        else if(s_in == "empty")
        {
            cout << (int)q.empty() << '\n';
        }
        else if(s_in == "front")
        {
            if(q.empty()) cout << -1 << '\n';
            else
            {
                cout << q.front() << '\n';
            }
        }
        else if(s_in == "back")
        {
            if(q.empty()) cout << -1 << '\n';
            else
            {
                cout << q.back() << '\n';
            }
        }
    }
    return 0;
}<file_sep>/7576.cpp
#include <iostream>
#include <queue>

using namespace std;

int N, M;
int arr[1000][1000];
bool visited[1000][1000];
int ans = 0, cnt = 0;
queue<pair<int, int>> q;

int idx[4] = {-1, 1, 0, 0};
int idy[4] = {0, 0, -1, 1};

void BFS()
{
    while(!q.empty())
    {
        pair<int, int> parent = q.front();
        int p_row = parent.first, p_column = parent.second;
        q.pop();
        for(int i = 0; i < 4; ++i)
        {
            int c_row = p_row + idx[i], c_column = p_column + idy[i];
            if(!visited[c_row][c_column] &&
                0 <= c_row && c_row < N &&
                0 <= c_column && c_column < M &&
                arr[c_row][c_column] == 0
                )
            {
                q.push({c_row, c_column});
                visited[c_row][c_column] = true;
                arr[c_row][c_column] = arr[p_row][p_column] + 1;
                ans = max(ans, arr[c_row][c_column] - 1);
                ++cnt;
            }
        }

    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> M >> N;
    
    for(int n = 0; n < N; ++n)
    {
        for(int m = 0; m < M; ++m)
        {
            cin >> arr[n][m];
        }
    }

    for(int n = 0; n < N; ++n)
    {
        for(int m = 0; m < M; ++m)
        {
            if(arr[n][m] == 1)
            {
                q.push({n, m});
                visited[n][m] = true;
                ++cnt;
            }
            if(arr[n][m] == -1)
            {
                ++cnt;
            }
        }
    }
    BFS();
    if(cnt != M*N) cout <<  -1 << endl;
    else cout << ans;
}<file_sep>/[try]15881.cpp
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> getPi(string p)
{
    int m = p.size(), j = 0;
    vector<int> pi(m, 0);
    for(int i = 1; i < m; ++i)
    {
        while(j > 0 && p[i] != p[j]) j = pi[i-1];
        if(p[i] == p[j]) p[i] = ++j;
    }
    return pi;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, ans = 0, count = 0;
    cin >> n;
    string s;
    cin >> s;
    
    return 0;
}<file_sep>/14501.cpp
#include <stdio.h>

using namespace std;

int maximize(const int &a, const int &b)
{
    return a > b ? a : b;
}

int main()
{
    int N;
    scanf("%d", &N);
    int T[N+1], P[N+1], dp[N+1], max = 0;   //dp[N]은 N일을 반드시 포함하면서 N일까지의 최댓값이다.
    for(int i = 1; i <= N; ++i) scanf("%d %d", &T[i], &P[i]);
    for(int i = 1; i <= N; ++i)
    {
        dp[i] = P[i];
        if(i + T[i] > N + 1) dp[i] = 0;
        else
        {
            for(int j = 1; j < i; ++j)
            {
                if(j + T[j] <= i) dp[i] = maximize(dp[i], dp[j] + P[i]);
            }
        }
        max = maximize(max, dp[i]);
    }
    printf("%d", max);
    return 0;
}<file_sep>/11053.cpp
#include <iostream>

using namespace std;

int A[1001];
int dp[1001];

int max(const int &a, const int &b)
{
    return a > b ? a : b;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, max_len = 0;
    cin >> N;
    for(int i = 1; i <= N; ++i)
    {
        cin >> A[i];
    }
    for(int i = 1; i <= N; ++i)
    {
        for(int j = 1; j <= i; ++j)
        {
            if(A[i] > A[j] && dp[j] > dp[i])
            {
                dp[i] = dp[j];
            }
        }
        ++dp[i];
        max_len = max(max_len, dp[i]);
    }
    cout << max_len;
    return 0;
}<file_sep>/1417.cpp
#include <iostream>
#include <queue>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, dasom, ans = 0;
    priority_queue<int> pq;    
    cin >> N;
    cin >> dasom;
    for(int n = 1; n < N; ++n){
        int temp;
        cin >> temp;
        pq.push(temp);
    }
    while(!pq.empty() && dasom <= pq.top()){
        ++dasom;
        ++ans;
        int temp = pq.top();
        pq.pop();
        pq.push(temp-1);
    }
    cout << ans;
}<file_sep>/[try]12015.cpp
#include <stdio.h>

using namespace std;

int max(const int &a, const int &b)
{
    return a > b ? a : b;
}

int main()
{
    int N;
    scanf("%d", &N);
    int A[N], dp[1000000] = {0}, ans = 0; 
    for(int n = 0; n < N; ++n) scanf("%d", &A[n]);
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < i; ++j)
        {
            if(A[j] < A[i]) dp[i] = max(dp[i], dp[j]);
        }
        ++dp[i];
        ans = max(ans, dp[i]);
    }
    printf("%d", ans);
    return 0;
}<file_sep>/1780.cpp
#include <iostream>

using namespace std;

int N, m_one, zero, p_one;
int M[2187][2187];

void getinput()
{
    cin >> N;
    
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            cin >> M[i][j];
        }
    }
}

void dc(int x, int y, int size)
{
    int temp = M[x][y];
    bool check = true;
    for(int i = x; i < x + size; ++i)
    {
        for(int j = y; j < y + size; ++j)
        {
            if(temp != M[i][j])
            {
                check = false;
                break;
            }
        }
    }

    if(check)
    {
        if(M[x][y] == -1)
        {
            ++m_one;
        }
        if(M[x][y] == 0)
        {
            ++zero;
        }
        if(M[x][y] == 1)
        {
            ++p_one;
        }
    }
    else
    {
        for(int i = 0; i < 3; ++i)
        {
            for(int j = 0; j < 3; ++j)
            {
                dc(x + i * size/3, y + j * size/3, size/3);
            }
        }
    }
}

void solve()
{
    getinput();
    dc(0,0,N);
    cout << m_one << '\n' << zero << '\n' << p_one;
}

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

    solve();
    return 0;
}<file_sep>/1992.cpp
#include <iostream>

using namespace std;

int N = 0;
int M[64][64];

void getinput()
{
    cin >> N;
    char temp;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            cin >> temp;
            M[i][j] = int(temp) - 48;
        }
    }
}

void quadtree(int x, int y, int size)
{
    int temp = M[x][y];
    bool check = true;
    for(int i = x; i < x + size; ++i){
        for(int j = y; j < y + size; ++j){
            if(temp != M[i][j]){
                check = false;
                break;
            } 
        }
    }
    if(check)
    {
        cout << temp;
    }

    else
    {
        cout << '(';
        int half = size / 2;
        quadtree(x, y, half);
        quadtree(x, y + half, half);
        quadtree(x + half, y ,half);
        quadtree(x + half, y + half , half);
        cout << ')';
    }
}

void solve()
{
    getinput();
    quadtree(0, 0, N);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();

    return 0;
}<file_sep>/12865.cpp
#include <stdio.h>
#include <algorithm>

using namespace std;

int dp[100001];

int main()
{
    int N, K, W, V;
    scanf("%d %d", &N, &K);

    for(int n = 0; n < N; ++n)
    {
        scanf("%d %d", &W, &V);
        for(int j = K; j >= W; --j)
        {
            dp[j] = max(dp[j-W] + V, dp[j]);
        }
    }
    printf("%d", dp[K]);

    return 0;
}<file_sep>/1766.cpp
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, a, b;

    priority_queue<int, vector<int>, greater<int>> queue;


    cin >> N >> M;

    int in_degree[N+1];
    vector<int> edge[N+1];
        
    for(int i = 0; i <= N; ++i)
    {
        in_degree[i] = 0;
    }

    for(int m = 0; m < M; ++m)
    {
        cin >> a >> b;
        edge[a].push_back(b);
        in_degree[b]++;
    }
    
    for(int i = 1; i <= N; ++i)
    {
        if(!in_degree[i])
        {
            queue.push(i);
        }
    }
    
    while(!queue.empty())
    {
        int vec = queue.top();
        queue.pop();
        cout << vec << " ";
        for(int i : edge[vec])
        {
            in_degree[i]--;
            if(!in_degree[i])
            {
                queue.push(i);
            }
        }
    }
}
<file_sep>/15651.cpp
#include <iostream>

using namespace std;

int N, M;
int arr[7] = {0,};

void backTrack(int height) {
    if(height == M) {
        for(int i = 0; i < M; ++i) {
            cout << arr[i] << " ";
        }
        cout << '\n';
        return;
    }

    for(int i = 1; i <= N; ++i) {
        arr[height] = i;
        backTrack(height + 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    backTrack(0);
    return 0;
}
<file_sep>/1904.cpp
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    if(N <= 3) cout << N;
    else{
        int a = 1, b = 2, c;
        
        for(int i = 3; i <= N; ++i){
            c = (a + b) % 15746;
            a = b;
            b = c;
        }
        cout << c;
    }
    
    return 0;
}<file_sep>/11401.cpp
#include <iostream>

using namespace std;

int p = 1e9 + 7;

long long power(long long a, long long b)
{
    if(b == 0) return 1;
    
    long long ans = power(a, b / 2);
    ans = (ans * ans) % p;

    if(b % 2 != 0) ans = (ans * a) % p;

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, K;
    cin >> N >> K;

    long long A = 1, B = 1;
    if(N - K < K)  K = N - K;
    for(int n = N-K+1; n <= N; ++n)
    {
        A *= n;
        A %= p;
    }

    for(int k = 1; k <= K; ++k)
    {
        B *= k;
        B %= p;
    }

    long long cal = A * power(B, p-2);
    cal %= p;
    cout << cal;
    
    return 0;
}<file_sep>/1629.cpp
#include <iostream>

using namespace std;

long long power(int a, int b, int c)
{
    if(b == 0) return 1;
    long long ans = power(a, b / 2, c);
    ans = (ans * ans) % c;

    if(b % 2 == 0)
    {   
        return ans;
    }
    else
    {
        ans = (ans * a) % c;
        return ans;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int A, B, C;
    cin >> A >> B >> C;
    cout << power(A,B,C);
}<file_sep>/13305.cpp
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, price, min = 1e9 + 1;
    long long ans = 0;
    cin >> N;
    int length[N-1];
    for(int i = 0; i < N-1; ++i) cin >> length[i];

    for(int i = 0; i < N-1; ++i)
    {
        cin >> price;
        min = min < price ? min : price;
        ans += (long long)min * length[i];
    }
    cout << ans;
    return 0;
}<file_sep>/15652.cpp
#include <iostream>
#include <vector>

using namespace std;

void backTrack(int height, int N, int M, int * arr) {
    if(height == M) {
        for(int i = 0; i < M; ++i) {
            cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }

    for(int i = 1; i <= N; ++i) {
        if(arr[0] == 0 || arr[height-1] <= i) {
            arr[height] = i;
            backTrack(height+1, N, M, arr);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    int arr[M];
    fill(arr, arr + M, 0);
    backTrack(0, N, M, arr);
    return 0;
}<file_sep>/1449.cpp
#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
    int N, L;
   scanf("%d %d", &N, &L);
    int input[N], start = -2000, ans = 0;

    for(int n = 0; n < N; ++n){
        scanf("%d", &input[n]);
    }

    sort(input, input + N);

    for(int n = 0; n < N; ++n){
        if(input[n] - start > L - 1){
            start = input[n];
            ++ans;
        }
    }
    printf("%d", ans);
    return 0;
}<file_sep>/9184.cpp
#include <iostream>

using namespace std;

const int maxn = 21;

int v[maxn][maxn][maxn];

int w(int a, int b, int c)
{
    if(a <= 0 || b <= 0 || c <= 0) return 1;
    
    else if(a > 20 || b > 20 || c > 20) return w(20, 20, 20);
    
    if(!v[a][b][c]){
        if(a < b && b < c){
            v[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
        }
        else{
            v[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
        }
    }
    
    return v[a][b][c];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int a, b, c;
    while(true)
    {
        cin >> a >> b >> c;
        if(a == -1 && b == -1 && c == -1) break;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << '\n';
    }
}<file_sep>/1193.cpp
#include <stdio.h>

int main(){
    int numerator = 1, denominator = 1, count = 0, X;
    scanf("%d", &X);
    while((count * (count + 1)) / 2 < X){
        ++count;
    }
    X -= (((count-1) * count) / 2 + 1);
    if(count % 2 == 0){
        numerator = 1;
        denominator = count;
        while(X != 0){
            ++numerator;
            --denominator;
            --X;
        }
    }
    else{
        numerator = count;
        denominator = 1;
        while(X != 0){
            --numerator;
            ++denominator;
            --X;
        }
    }
    printf("%d/%d",numerator,denominator);
}<file_sep>/1181.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

bool compare(string a, string b){
    if(a.length() == b.length()) return a < b;
    else return a.length() < b.length();

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    vector<string> arr;
    string temp;
    for(int i = 0; i < N; ++i){
        cin >> temp;
        arr.push_back(temp);
    }
    sort(arr.begin(), arr.end(), compare);

    for(int i = 0; i < arr.size() - 1;){
        if(arr[i] == arr[i+1]) arr.erase(arr.begin()+i);
        else ++i;
    }

    for(int i = 0; i < arr.size(); ++i){
        cout << arr[i] << '\n';
    }
}<file_sep>/1316.cpp
#include <stdio.h>
#include <string.h>

int main(){
    /* There are three cases when we check each alphabet.
     * 1. First met but not a last letter.
     * 2. First met and last letter.
     * 3. Alread met
     * 
     * The case.1 We just do next iteration, because it's not a 
     * last so we can act on case.2.
     * 
     * The case.2 We 'mark' the letter was encountered.
     * 
     * The case.3 Erase the 'mark' which we've done on case.2
     */

    // get input N
    // For each iteration, get input[101] and alphabet[26] = {0}
    // If (alphabet[a[i] - 'a'] > 0), count = 0; break;
    // else If input[i] != input[i+1], alphabet[array[i] - 'a'] = 1
    // sum += count;
    
    int N = 0, sum = 0;
    scanf("%d", &N);
    for(int n = 0; n < N; ++n){
        char input[101];
        scanf("%s", input);
        int alphabet[26] = {0}, count = 1;
        int length = strlen(input);
        for(int i = 0; i < length; ++i){
            if(alphabet[input[i] - 'a'] > 0){
                count = 0;
                break;
            }
            else if(input[i] != input[i+1]){
                alphabet[input[i] - 'a'] = 1;
            }
        }
        sum += count;
    }
    printf("%d", sum);
}<file_sep>/9251.cpp
#include <iostream>
#include <string>

using namespace std;

int dp[1001][1001];

int LCS(string s1, string s2)
{
    int n = s1.length();
    int m = s2.length();
    for(int x = 0; x < n; ++x) dp[x][0] = 0;
    for(int y = 0; y < m; ++y) dp[0][y] = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            if(s1[i] == s2[j]){
                dp[i+1][j+1] = dp[i][j] + 1;
            }
            else if(dp[i][j+1] >= dp[i+1][j])
            {
                dp[i+1][j+1] = dp[i][j+1];
            }
            else dp[i+1][j+1] = dp[i+1][j];
        }
    }
    return dp[n][m];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s1, s2;
    cin >> s1 >> s2;
    cout << LCS(s1, s2);

    return 0;
}<file_sep>/17298.cpp
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, temp = 0, index = 0;
    cin >> N;
    stack<int> s;
    vector<int> v, ans(N, -1);
    for(int i = 0; i < N; ++i)
    {
        cin >> temp;
        v.push_back(temp);
    }
    
    s.push(0);
    for(int i = 1; i < N; ++i)
    {
        while(!s.empty() && v[s.top()] < v[i])
        {
            ans[s.top()] = v[i];
            s.pop();

        }
        s.push(i);
    }

    for(int i = 0; i < N; ++i)
    {
        cout << ans[i] << ' '; 
    }  
}
/* 
 *  stack s = {s1, s2, ... , s.top} s.t. v[s1] >= v[s2] >= ... >= v[s.top]
 *  1. v[i] <= v[s.top]  --> s = {s1, s2, ... , s.top, s[i]} s.t. v[s1] >= v[s2] >= ... >= v[s.top] >= v[input]
 *  2. v[i] >  v[s.top]  --> while(!s.empty() && v[s.top] < v[i]) ans[s.top] = v[i], s.pop()
 */ <file_sep>/7568.cpp
#include <stdio.h>

int main(){
    int N;
    scanf("%d", &N);
    int arr[2 * N], rank[N];

    for(int i = 0; i < N; ++i){
        rank[i] = 0;
    }

    for(int i = 0; i < N; ++i){
        scanf("%d %d", &arr[i], &arr[i + N]);
    }

    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(arr[i] < arr[j] && arr[i + N] < arr[j + N]){
                ++rank[i];
            }
        }
    }

    for(int i = 0; i < N; ++i){
        printf("%d ", rank[i] + 1);
    }
}<file_sep>/10250.cpp
#include <iostream>

int main(){
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    
    for(int i = 0; i < T; ++i){
        int H = 0, W = 0, N = 0;
        cin >> H >> W >> N;
        int floor = 0, room = 0;
        floor = (N + (H - 1)) % H  + 1;
        room  = (N - 1) / H + 1; 
        int num =  floor * 100 + room;
        cout << num << "\n";
    }
}


/* 
 *  H01 H02     HW
 *  ...
 *  301
 *  201 202     2W
 *  101 102 ... 1W
 * 
 *  n(mod H)             :  0 ~ H - 1, n = 1 -> 1
 *  n(mod H) + 1         :  1 ~ H    , n = 1 -> 2
 *  n + H - 1(mod H) + 1 :  0 ~ H - 1, n = 1 -> 1
 */ <file_sep>/1080.cpp
#include <stdio.h>

using namespace std;

int A[50][50], B[50][50];

void change(int i, int j)
{
    for(int x = i; x < i + 3; ++x){
        for(int y = j; y < j + 3; ++y)
        {
            if(A[x][y] == 1) A[x][y] = 0;
            else if(A[x][y] == 0) A[x][y] = 1;
        }
    }
}

bool check_matrix(int i, int j)
{
    for(int x = 0; x < i; ++x){
        for(int y = 0; y < j; ++y)
        {     
            if(A[x][y] != B[x][y]) return false;
        }
    }
    return true;    
}

int main(){

    int N, M, ans = 0;
    scanf("%d %d", &N, &M);
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            scanf("%1d", &A[i][j]);
        }
    }
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            scanf("%1d", &B[i][j]);
        }
    }

    for(int i = 0; i < N - 2; ++i){
        for(int j = 0; j < M - 2; ++j){
            if(A[i][j] != B[i][j]){
                change(i, j);
                ++ans;
            }
        }
    }
    if(!check_matrix(N, M)){
        ans = -1;
    }

    printf("%d", ans);

    return 0;
}<file_sep>/1543.cpp
#include <iostream>
#include <string>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string document, search;
    getline(cin, document);
    getline(cin, search);
    int s_len = search.length(), jump = -1, d_len = document.length(), ans = 0;
    bool flag = true;
    for(int i = 1; i < s_len; ++i){
        if(search[0] == search[i]){
            jump = i;
            break;
        }
    }
    for(int i = 0; i < d_len;){
        for(int j = 0; j < s_len; ++j){
            if(document[i+j] != search[j]){
                if(j <= 1) ++i;
                else if(jump == -1 || j < jump) i += j;
                else i += jump;
                flag = false;
                break;
            }
        }
        if(flag){
            ++ans;
            i += s_len;
        }
        flag = true;
    }

    cout << ans;
    return 0;
}<file_sep>/14325.cpp
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, a;
    priority_queue<int> pq;

    cin >> n;
    while(n--){
        cin >> a;
        if(a == 0)
        {
            if(pq.empty())
            {
                cout << -1 << '\n';
            }
            else
            {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
        else
        {
            while(a--)
            {
                int temp;
                cin >> temp;
                pq.push(temp);
            }
        }
    }
}<file_sep>/2178.cpp
#include <stdio.h>
#include <queue>

using namespace std;

int N, M;
int arr[100][100];
bool visited[100][100] = {false,};
int idx[4] = {-1, 1, 0, 0};
int idy[4] = {0, 0, -1, 1};

bool in_matrix(int row, int column)
{
    return (0 <= row && row < N && 0 <= column && column < M);
}

void BFS(int row, int column)
{
    queue<pair<int, int>> queue;
    queue.push({row, column});
    visited[row][column] = true;
    while(!queue.empty())
    {
        pair<int, int> parent = queue.front();
        queue.pop();
        int p_row = parent.first;
        int p_column = parent.second;

        for(int i = 0; i < 4; ++i)
        {
            int c_row = p_row + idx[i];
            int c_column = p_column + idy[i];
            if(in_matrix(c_row, c_column) && arr[c_row][c_column] && !visited[c_row][c_column])
            {
                queue.push({c_row, c_column});
                visited[c_row][c_column] = true;
                arr[c_row][c_column] = arr[p_row][p_column] + 1;
            }
        }

    }
}

int main()
{ 
    scanf("%d %d", &N, &M);
    
    for(int n = 0; n < N; ++n){
        for(int m = 0; m < M; ++m){
            scanf("%1d", &arr[n][m]);
        }
    }
    BFS(0, 0);

    printf("%d", arr[N-1][M-1]);
}<file_sep>/1932.cpp
#include <stdio.h>
#include <algorithm>

using namespace std;

int dp[500][500];

int main(){
    int n;
    scanf("%d", &n);

    for(int i = 0; i < n; ++i){
        for(int j = 0; j <= i; ++j){
            scanf("%d", &dp[i][j]);
        }
    }

    for(int i = 1; i < n; ++i){
        dp[i][0] = dp[i-1][0] + dp[i][0];
        dp[i][i] = dp[i-1][i-1] + dp[i][i];
        for(int j = 1; j < i; ++j){
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + dp[i][j];
        }
    }

    int temp = dp[n-1][0];

    for(int i = 1; i < n; ++i){
        temp = max(temp, dp[n-1][i]);
    }
    printf("%d",temp);
    return 0;
}<file_sep>/10844.cpp
#include <iostream>

using namespace std;

long long dp[101][10];    //dp[x][y]는 길이가 x이고 앞자리가 y인 수의 갯수 

int mod = 1000000000;

void stair(const int &n){
    for(int i = 1; i < 9; ++i){
        dp[n][i] = (dp[n-1][i-1] + dp[n-1][i+1]) % mod; 
    }
    dp[n][0] = dp[n-1][1] % mod; 
    dp[n][9] = dp[n-1][8] % mod;
}

int main()
{
    int N;
    long long sum = 0;
    cin >> N;
    for(int i = 0; i < 10; ++i){
        dp[1][i] = 1;
    }
    for(int n = 2; n <= N; ++n){
        stair(n);
    }
    for(int i = 1; i <= 9; ++i){
        sum += dp[N][i] % mod;
    }
    cout << sum % mod;
    return 0;
}<file_sep>/2606.cpp
#include <iostream>
#include <vector>

using namespace std;

int cnt = 0;
vector<int> edge[101];
bool visited[101] ={false,}; 

void DFS(int parent)
{
    visited[parent] = true;
    for(auto child : edge[parent]){
        if(!visited[child]){
            DFS(child);
            ++cnt;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int num_com, num_pair, a, b;
    cin >> num_com >> num_pair;
    for(int i = 0; i < num_pair; ++i){
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    DFS(1);

    cout << cnt;
}<file_sep>/2579.cpp
#include <iostream>
#include <algorithm>

using namespace std;

int stair[301];
int dp[301];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> stair[i];
    }

    dp[0] = stair[0];
    dp[1] = stair[1] + dp[0];
    dp[2] = max(stair[2] + stair[0], stair[2] + stair[1]);

    for(int i = 3; i < n; ++i){
       dp[i] = stair[i] + max(stair[i-1] + dp[i-3], dp[i-2]); 
    }
    cout << dp[n-1];
    return 0;
}<file_sep>/13301.cpp
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, ans;
    cin >> N;
    int dp[N];
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i < N; ++i)
    {
        dp[i] = dp[i-1] + dp[i-2];
    }
    if(N == 1) ans = 4;
    else if(N == 2) ans = 6;
    else
    {
        ans = 2 * (2 * dp[N-1] + dp[N-2]);
    }
    cout << ans;
    return 0;
}<file_sep>/10830.cpp
#include <iostream>
#include <vector>

using namespace std;

vector<vector<long long>> matrix_multi(vector<vector<long long>> A, vector<vector<long long>> B)
{
    long long length = A.size();
    vector<vector<long long>> temp(length, vector<long long>(length));
    for(long long i = 0; i < length; ++i)
    {
        for(long long j = 0; j < length; ++j)
        {
            long long term = 0;
            for(long long k = 0; k < length; ++k)
            {
                term += A[i][k] * B[k][j];
            }
            temp[i][j] = (term % 1000);
        }
    }
    return temp;
}

vector<vector<long long>> power(vector<vector<long long>> A, long long n, long long B)
{
    vector<vector<long long>> I(n, vector<long long>(n));
    for(long long i = 0; i < n; ++i)
    {
        I[i][i] = 1;
    }
    if(B == 0) return I;
    vector<vector<long long>> temp = power(A, n, B / 2);
    temp = matrix_multi(temp, temp);
    if(B % 2 != 0)
    {
        temp = matrix_multi(temp, A);
    }
    return temp;
}

void print(vector<vector<long long>> A)
{
    int n = A.size();
    for(long long i = 0; i < n; ++i)
    {
        for(long long j = 0; j < n; ++j)
        {
            cout << A[i][j] << ' ';
        }
        cout << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long N, B;
    cin >> N >> B;
    vector<vector<long long>> m(N, vector<long long>(N));

    for(long long i = 0; i < N; ++i)
    {
        for(long long j = 0; j < N; ++j)
        {
            cin >> m[i][j];
        }
    }
   
    print(power(m, N, B));

}<file_sep>/12018.cpp
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, mileage = 0, ans = 0;
    cin >> n >> m;
    int P, L;
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i = 0; i < n; ++i){
        cin >> P >> L;
        int temp;
        priority_queue<int, vector<int>, greater<int>> tempq;
        for(int p = 0; p < P; ++p){
            cin >> temp;
            tempq.push(temp);
        }
        if(P >= L){
            while(P > L){
                tempq.pop();
                --P;
            }
            pq.push(tempq.top());
        }
        else{
            pq.push(1);
        }
    }
    while(mileage + pq.top() <= m && ans < n){
        mileage += pq.top();
        ++ans;
        pq.pop();
    }
    cout << ans;
}<file_sep>/9625.cpp
#include <iostream>

using namespace std;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int K;
    cin >> K;
    pair<int, int> dp[K+1];
    dp[0] = make_pair(1,0);
    for(int i = 1; i <= K; ++i)
    {
        dp[i] = make_pair(dp[i-1].second, dp[i-1].first + dp[i-1].second);
    }
    cout << dp[K].first << " " << dp[K].second;

    return 0;
}<file_sep>/9465.cpp
#include <iostream>
#include <algorithm>

using namespace std;

int sticker[100001][2];
int dp[100001][2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T, n;
    cin >> T;
    while(T--){
        cin >> n;

        for(int j = 0; j < 2; ++j){
            for(int i = 0; i < n; ++i){
                cin >> sticker[i][j];
            }
        }
        
        dp[0][0] = sticker[0][0];
        dp[0][1] = sticker[0][1];
        dp[1][0] = sticker[1][0] + dp[0][1];
        dp[1][1] = sticker[1][1] + dp[0][0];

        for(int i = 2; i < n; ++i){
            dp[i][0] = max(dp[i-1][1], max(dp[i-2][0], dp[i-2][1])) + sticker[i][0];
            dp[i][1] = max(dp[i-1][0], max(dp[i-2][0], dp[i-2][1])) + sticker[i][1];
        }
        cout << max(dp[n-1][0], dp[n-1][1]) << '\n';
    }
    return 0;
}<file_sep>/2630.cpp
#include <iostream>
#include <cmath>

using namespace std;

int N, blue, white;
int M[128][128];

void getinput()
{
    cin >> N;
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            cin >> M[i][j];
        }
    }
}

void quadtree(int x, int y, int size)
{
    int temp_blue = 0;

    for(int i = x; i < x + size; ++i)
    {
        for(int j = y; j < y + size; ++j)
        {
            if(M[i][j] == 1) ++temp_blue;
        }
    }
    if(temp_blue == 0)
    {
        ++white;
        return;
    }
    else if(temp_blue == size * size)
    {
        ++blue;
        return;
    }
    int half  = size / 2;
    quadtree(x, y, half);
    quadtree(x, y + half, half);
    quadtree(x + half, y, half);
    quadtree(x + half, y + half, half);

}

void solve()
{
    quadtree(0,0,N);
    cout << white << '\n' << blue << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    getinput();
    solve();

    return 0;
}<file_sep>/11054_2.cpp
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    int A[N], front_len[1000] = {0}, back_len[1000] = {0}, bitonic_len = 0;
    for(int i = 0; i < N; ++i)
    {
        cin >> A[i];
    }

    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < i; ++j)
        {
            if(A[j] < A[i])
            {
                front_len[i] = max(front_len[i], front_len[j]);
            }
            if(A[N-1-j] < A[N-1-i])
            {
                back_len[N-1-i] = max(back_len[N-1-i], back_len[N-1-j]);
            }
        }
        ++front_len[i];
        ++back_len[N-1-i];
    }
    
    for(int i = 0; i < N; ++i)
    {
        bitonic_len = max(bitonic_len, front_len[i] + back_len[i]);
    }

    cout << bitonic_len - 1;
    return 0;
}<file_sep>/1439.cpp
#include <iostream>
#include <string>

using namespace std;

int main(){
    int cnt1 = 0, cnt2 = 0;
    string S;
    char c;
    cin >> S;
    bool flag = true;
    int n = S.length();
    for(int i = 0; i < n;){
        c = S[i];
        while(c == S[i] && i < n)
        {
            ++i;
        }
        if(flag){
            ++cnt1;
            flag = false;
        }
        else{
            ++cnt2;
            flag = true;
        }
    }
    cout << (cnt1 < cnt2 ? cnt1 : cnt2); 
    return 0;
}<file_sep>/1427_2.cpp
#include <stdio.h>
#include <algorithm>

bool compare(int a, int b){
    return b < a;
}

int main(){
    char arr[11];
    int i;
    for(i = 0; i < 10; ++i){
        char c = getchar();
        if(c == '\n'){
            arr[i] = 0;
            break;
        }
        arr[i] = c;
    }
    std::sort(arr, arr + i, compare);
    printf("%s", arr);
}<file_sep>/2217.cpp
#include <iostream>
#include <algorithm>

using namespace std;

bool compare(const int a, const int b)
{
    return a > b;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, ans = 0;
    cin >> N;
    int W[N];
    for(int i = 0; i < N; ++i) cin >> W[i];
    sort(W, W + N, compare);
    for(int i = 0; i < N; ++i)
    {
        if(ans < W[i] * (i+1))
        {
            ans = W[i] * (i+1) ;
        }
    }
    cout << ans;
    return 0;
}<file_sep>/11052.cpp
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    int p[N+1], dp[N+1];
    for(int i = 1; i <= N; ++i)
    {
        cin >> p[i];
    }
    for(int i = 1; i <= N; ++i)
    {
        dp[i] = p[i];
        for(int j = 1; j < i; ++j)
        {
            dp[i] = max(dp[i], dp[j] + dp[i-j]);
        }
    }
    cout << dp[N];
    return 0;
}<file_sep>/5622.cpp
#include <stdio.h>
#include <string.h>
int main(){
    char input[15];
    scanf("%s", input);
    int sum = 0;
    int length = strlen(input);
    for(int i = 0; i < length; ++i){
        if('A' <= input[i] && input[i] <= 'O') sum += (input[i] - 'A') / 3 + 3;
        else if('P' <= input[i] && input[i] <= 'S') sum += 8;
        else if('T' <= input[i] && input[i] <= 'V') sum += 9;
        else if('W' <= input[i] && input[i] <= 'Z') sum += 10;
    }
    printf("%d", sum);
}<file_sep>/2075.cpp
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, temp;
    cin >> N;
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int n = 0; n < N; ++n){
        for(int m = 0; m < N; ++m){
            cin >> temp;
            if(pq.size() == N && temp <= pq.top()) continue;
            pq.push(temp);
            if(pq.size() > N) pq.pop();
        }
    }
    cout << pq.top();
}<file_sep>/11444.cpp
#include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<long long>> matrix;
int p = 1000000007;
matrix I = {{1,0},{0,1}};
matrix m = {{1,1},{1,0}};

matrix operator *(matrix a, matrix b)
{
    
    matrix temp(2, vector<long long>(2));
    for(int i = 0; i < 2; ++i){
        for(int j = 0; j < 2; ++j){
            for(int k = 0; k < 2; ++k){
                temp[i][j] += a[i][k] * b[k][j];
            }
            temp[i][j] %= p;
        }
    }
    return temp;
}

matrix Fibonacci(const matrix a, long long n)
{
    if(n == 1) return m;
    matrix temp = Fibonacci(a, n / 2);
    temp = temp * temp;
    if(n % 2 != 0)
    {
        temp = temp * a;
    }
    return temp;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long N;
    cin >> N;
    
    cout << Fibonacci(m, N)[0][1];

}

/*
 * Fn = Fn-1 + Fn-2
 * Fn   Fn-1           (1 1) Fn-1  Fn-2 ... (1 1)^n-1  F2 F1  =  (1 1)^n
 * Fn-1 Fn-2           (1 0) Fn-2  Fn-3 ... (1 0)      F1 F0     (1 0)
 * 
 * 
 * 
 * 
 */<file_sep>/15650.cpp
#include <iostream>
#include <vector>

using namespace std;

void backTrack(int height, int N, int M, bool *visited, vector<int> answer) {
    if(height == M) {
        for(int i = 0; i < M; ++i) {
            cout << answer[i] << " ";
        }
        cout << endl;
        return;
    }

    for(int i = 1; i <= N; ++i) {
        if(!visited[i] && (answer.empty() || answer.back() < i)) {
            visited[i] = true;
            answer.push_back(i);
            backTrack(height+1, N, M, visited, answer);
            visited[i] = false;
            answer.pop_back();
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M;
    cin >> N >> M;
    bool visited[9]{0};
    vector<int> answer;
    backTrack(0, N, M, visited, answer);
    return 0;
}<file_sep>/2108.cpp
#include <stdio.h>

void merge(int *arr, int *sorted, int start, int middle, int end){
    
    int l = start, r = middle + 1, i = start;
    
    while(l <= middle && r <= end){
        if(arr[l] > arr[r]){
            sorted[i] = arr[r];
            ++r;
        }
        else{
            sorted[i] = arr[l];
            ++l;
        }
        ++i;
    }

    if(l > middle){
        while(r <= end){
            sorted[i] = arr[r];
            ++r;
            ++i;
        }
    }
    else{
        while(l <= middle){
            sorted[i] = arr[l];
            ++l;
            ++i;
        }
    }

    for(int k = start; k <= end; ++k){
        arr[k] = sorted[k];
    }
}

void merge_sort(int *arr, int *sorted, int start, int end){
    if(start < end){
        int middle = (start + end) / 2;
        merge_sort(arr, sorted, start, middle);
        merge_sort(arr, sorted, middle + 1, end);
        merge(arr, sorted, start, middle, end);
    }
}

int main(){
    int N;
    scanf("%d", &N);
    int arr[N], sorted[500000] = {0}, min = 4000, max = -4000;
    int  count[8001] = {0}, max_count  = 0, check = 0, mode = 0;
    double mean = 0;

    for(int i = 0; i < N; ++i){
        scanf("%d", &arr[i]);
        mean += arr[i];
        if(arr[i] > max) max = arr[i];
        if(arr[i] < min) min = arr[i];
        ++count[arr[i] + 4000];
        if(count[arr[i] + 4000] > max_count) max_count = count[arr[i] + 4000];
    }

    for(int k = 0; k <= 8000; ++k){
        
        if(count[k] == max_count){
            ++check;
        }
    }

    for(int k = 0; k <= 8000; ++k){
        if(check == 1 && count[k] == max_count){
            mode = k - 4000;
            break;
        }
        else{
            if(count[k] == max_count){
                check = 1;
            }
        }
    }

    merge_sort(arr, sorted, 0, N - 1);

    // print arithmetic mean
    mean /= N;
    printf("%.0f\n", mean);

    // print median
    printf("%d\n", arr[N/2]);
    
    // print mode
    printf("%d\n", mode);
    
    // print range
    printf("%d\n", max - min);
}<file_sep>/2748.cpp
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    long long Fn[n+1];
    Fn[0] = 0;
    Fn[1] = 1;
    for(int i = 2; i <= n; ++i)
    {
        Fn[i] = Fn[i-1] + Fn[i-2];
    }
    cout << Fn[n];
    return 0;
}<file_sep>/1339.cpp
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

bool rev(const int a, const int b){
    return a > b;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, alphabet[26]={0,}, ans = 0;
    cin >> N;
    string temp;
    for(int n = 0; n < N; ++n){
        cin >> temp;
        int len = temp.length();
        for(int j = 0; j < len; ++j){
            alphabet[temp[j]-'A'] += pow(10, len-1-j);
        }
    }

    sort(alphabet, alphabet + 26, rev);

    for(int i = 0; i < 10; ++i){
        ans += alphabet[i] * (9-i);
    }
    
    cout << ans;
}<file_sep>/2751.cpp
#include <stdio.h>

// merge() is a function that combine splited L-array and R-array into the one array;
void merge(int *arr, int *sorted, int &start, int &middle, int &end){
    int l = start;
    int r = middle + 1;
    int i = start;

    while(l <= middle && r <= end){
        if(arr[l] > arr[r]){
            sorted[i] = arr[r];
            ++i;
            ++r;
        }
        else{
            sorted[i] =  arr[l];
            ++i;
            ++l;
        }
    }

    if(l > middle){
        while(r <= end){
            sorted[i] = arr[r];
            ++i;
            ++r;
        }
    }
    else{
        while(l <= middle){
            sorted[i] = arr[l];
            ++i;
            ++l;
        }
    }
    for(int k = start; k <= end; ++k){
        arr[k] = sorted[k];
    }
}

// merge-sort() is a function that splite the array and combine them again to use merge();
void merge_sort(int *arr, int *sorted, int &begin, int &end){
    if(begin < end){
        int center = (end +  begin) / 2;
        int center2 = center + 1;
        merge_sort(arr, sorted, begin, center);
        merge_sort(arr, sorted, center2, end);
        merge(arr, sorted, begin, center, end);
    }
}

int main(){
    int N;
    int begin = 0;
    scanf("%d", &N);
    int arr[N];
    int sorted[N];
    for(int i = 0; i < N; ++i){
        scanf("%d", &arr[i]);
    }
    int end = N - 1;
    merge_sort(arr, sorted, begin, end);

    for(int i = 0; i < N; ++i){
        printf("%d\n", arr[i]);
    }
}<file_sep>/17503.cpp
#include <iostream>
#include <queue>

using namespace std;

struct compare_list{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        if(a.second == b.second) return a.first < b.first;
        else return a.second > b.second; 
    }
};

struct compare_chosen{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        if(a.first == b.first) return a.second < b.second;
        else return a.first > b.first; 
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare_list> list;
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare_chosen> chosen;

    int N, M, K, v, c, level = 0, preference = 0;
    cin >> N >> M >> K;
    
    for(int i = 0; i < K; ++i)
    {
        cin >> v >> c;
        list.push(pair<int, int>(v, c));
    }

    for(int i = 0; i < K; ++i)
    {
        chosen.push(list.top());
        preference += list.top().first;
        level = max(level, list.top().second);
        list.pop();
        if(chosen.size() > N)
        {
            preference -= chosen.top().first;
            chosen.pop();
        }
        if(chosen.size() == N && preference >= M)
        {
            cout << level;
            return 0;
        }
    }
    
    if(preference < M)
    {
        cout << -1;
        return 0;
    }

}<file_sep>/1003.cpp
#include <stdio.h>

using namespace std;

int fibo[41];

int fibonacci(const int &n)
{
    if(fibo[n] != 0) return fibo[n];
    else if(n <= 0){
        fibo[0] = 0;
        return 0;
    } 
    else if(n == 1)
    {
        fibo[1] = 1;
        return 1;
    } 
    else{
        return fibo[n] = fibonacci(n-1) + fibonacci(n-2);
    }
}

int main()
{
    int T, N;
    scanf("%d",&T);
    for(int t = 0; t < T; ++t)
    {
        scanf("%d", &N);
        if(N == 0) printf("%d %d\n", 1, 0);
        else if(N == 1) printf("%d %d\n", 0, 1);
        else{
            printf("%d %d\n", fibonacci(N-1), fibonacci(N));
        }
    }
} <file_sep>/10872.cpp
#include <stdio.h>

int main(){
    int N, answer = 1;
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i){
        answer *= i;
    }
    printf("%d", answer);
}<file_sep>/2980.cpp
#include <stdio.h>

int main(){
    int input1 = 0, input2 = 0;
    scanf("%d %d", &input1, &input2);
    input1 = 100 * (input1 % 10) + 10 * ((input1 % 100) / 10) + input1 / 100;
    input2 = 100 * (input2 % 10) + 10 * ((input2 % 100) / 10) + input2 / 100;
    if(input1 > input2) printf("%d", input1);
    else printf("%d", input2);

}