모든 경우이 수를 다 보는 것은 1초의 제한시간과 30만의 입력값을 보았을 때 당연히 되지 않는구나~ 라고 느껴야 한다.

때문에 뭔가 다른 방법을 생각해야 한다. 이 문제의 경우는 인접한 수끼리의 차를 정렬한 뒤 N-K 만큼 앞부터 원소를 고르는 식으로 집합을 생각하면 간단하다. 이와 같이 구현만 하면 문제는 간단히 풀린다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
deque<int> arr;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a, b;
    cin >> a >> b;
    
    int cur, prev = 0;
    for (int i = 0; i < a; i++) {
        cin >>  cur;
        if (prev == 0) {
            prev = cur;
            continue;
        }
        else {
            arr.push_back(cur - prev);
            prev = cur;
        }
    }

    sort(arr.begin(), arr.end());

    LL res = 0;
    for (int k = 0; k < a-b; k++) {
        int cx = arr.front();
        arr.pop_front();
        res += cx;
    }
    cout << res;
    // 2 2 1 5
    return 0;
}

경우를 잘 나눠야 하는 문제이다. 일단 문제의 시간제한 1초를 봤을 때 10만의 입력값으로 통과하기 위해서는 답은 O(Nlog(N)) 의 시간 제한으로 풀 수 있어야 한다. 때문에 이분탐색, 세그먼트 트리 등등의 알고리즘을 떠올릴 수 있다.

이 문제의 경우에는 다른 자료구조가 필요한 것이 아니라 전체 경우가 최대값을 가지기 위해서는 특정 경우로 나뉜다 정도만 알면 풀 수 있다.

전체 최대값을 가질 수 있는 경우는 다음과 같다.

1. "벌꿀 - 벌 - 벌" 순서로 있는 경우
2. "벌 - 벌 - 벌꿀" 순서로 있는 경우
3. "벌 - 벌꿀 - 벌" 순서로 있는 경우

각 경우마다 왼쪽 끝, 오른쪽 끝에 위치해야하고, 중간 특정 지점이 위치해야 한다.

위 3가지 경우에 대해 값을 다 확인하며 최대값을 구할 때 O(N) 의 복잡도를 이끌어 내기 위하여 누적합을 왼쪽, 오른쪽 방향으로 구해놓아야 한다. 그 후에는단순 선형탐색을 통해 답을 빠르게 구할 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
int arr[100001];
int r_sum[100001];
int l_sum[100001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        l_sum[i] = (i == 0) ? arr[i] : l_sum[i-1] + arr[i];
    }
    for (int i = n - 1; i >= 0; i--)
        r_sum[i] = (i == n-1) ? arr[i] : r_sum[i+1] + arr[i];
    

    int _max = 0;
    for (int i = 1; i < n - 1; i++) 
        if(_max < arr[i]) _max = arr[i];
    
    int answer = 0, a_res, c_res;
    for (int i = 1; i < n - 1; i++) {
        a_res = 0;
        // 오른쪽 끝이 벌꿀인 경우
        a_res += r_sum[i] - arr[i];
        a_res += r_sum[0] - arr[0] - arr[i];
        answer = max(answer, a_res);
				
				// 왼쪽 끝이 벌꿀인 경우
        c_res = 0;
        c_res += l_sum[i] - arr[i];
        c_res += l_sum[n - 1] - arr[n - 1] - arr[i];
        answer = max(answer, c_res);
    }

		// 가운데에 벌꿀이 있는 경우
    cout << max(answer, l_sum[n - 1] - arr[0] - arr[n - 1] + _max);
    
    return 0;
}

heap 2개를 가지고 Nlog(N) 의 시간 내로 중앙값을 뽑아내는 로직을 사용하면 쉽게 풀린다. heap 2개는 다음과 같다.

• 절반의 작은 값들을 저장하는 max heap
• 절반의 큰 값들을 저장하는 min heap

이 때 min heap 이 max heap 크기 이상의 특징을 계속 가지도록 한다면 홀 수 개의 값이 입력되었을 때 min heap 의 top 을 출력하도록 하면 쉽게 풀린다.

예를 들어 입력되는 수가 1, 5, 4, 3, 2 라고 해보자.

1. 1 이 들어오게 되면 먼저 min heap 에 넣는다.
2. 그 후 5가 들어오면 size 가 작은 max heap 에 넣는다.
3. 넣은 후 max heap 의 top과 min heap의 top 을 비교해서 max heap 의 것이 더 크다면 서로 top 을 swap 해준다.
4. 2~3 을 반복한다.

이렇게 되면 위에서 말했듯이 절반의 작은 값들은 max heap 에 저장되고, 절반의 큰 값들은 min heap 에 저장되어 중간값을 바로바로 꺼내어 확인할 수 있게 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int n, m;
int arr[10001];
priority_queue<int, vector<int>, greater<int>> minQ;
priority_queue<int, vector<int>, less<int>> maxQ;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int tc;
    cin >> tc;
    vector<int> ans;
    for (int i = 0; i < tc; i++) {
        cin >> n;
        ans.clear();
        memset(arr, 0, sizeof(arr));
        for (int j = 1; j <= n; j++) {
            cin >> arr[j];

            if (minQ.empty()) 
                minQ.push(arr[j]);
            else if (minQ.size() > maxQ.size()) 
                maxQ.push(arr[j]);
            else if (maxQ.size() <= maxQ.size()) 
                minQ.push(arr[j]);
            // 똑같음
            if (!maxQ.empty() && maxQ.top() > minQ.top()) {
                int temp = maxQ.top();
                maxQ.pop();
                maxQ.push(minQ.top());
                minQ.pop();
                minQ.push(temp);
            }

            if (j % 2 != 0) {
                ans.push_back(minQ.top());
            }
        }
        cout << ans.size() << endl;
        for (int i = 0, cnt = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
            cnt += 1;
            if (cnt % 10 == 0) cout << endl;
        }
        cout << endl;

        while (!maxQ.empty()) maxQ.pop();
        while (!minQ.empty()) minQ.pop();
    }

    return 0;
}

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

시간 복잡도가 1초이고, 입력값이 10만개, query 의 값이 만개 이므로 각 query 마다 log(N) 의 복잡도 내로 답이 나오도록 처리해야 문제가 풀리게 된다.

이를 위해 입력 시에만 Nlog(N) 의 복잡도가 걸리고 query 에 따른 값을 뽑아 낼 때는 log(N) 의 복잡도를 가지는 min heap, max heap 2개와 solved 된 문제를 체킹하기 위한 배열 1개가 잇으면 간단히 풀리게 된다.

단, solved 된 문제를 체킹할 때 해당 문제의 난이도를 배열에 저장함으로써 이 후 top 의 값이 체킹해두었던 난이도가 아니라면 pop 하고 다음 수를 보는 로직을 통해 문제를 해결할 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int n, a, b;
string tp;
int check[100001];
priority_queue<pii, vector<pii>, greater<pii>> minQ;
priority_queue<pii, vector<pii>> maxQ;

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        maxQ.push({ b, a });
        minQ.push({ b, a });
        check[a] = b;
    }

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tp;
        if (tp == "add") {
            cin >> a >> b;
            maxQ.push({ b, a });
            minQ.push({ b, a });
            check[a] = b;
        }
        else if (tp == "recommend") {
            cin >> a;
            if (a == 1) {
                while (check[maxQ.top().second] != maxQ.top().first) {
                    maxQ.pop();
                }
                cout << maxQ.top().second << endl;
            }
            else if (a == -1) {
                while (check[minQ.top().second] != minQ.top().first) {
                    minQ.pop();
                }
                cout << minQ.top().second << endl;
            }
        }
        else if (tp == "solved") {
            cin >> a;
            check[a] = -1;
        }
    }
    return 0;
}

단순한 그래프 탐색을 진행하게 되면 바로 시간이 터지게 된다.

오른쪽위 → 오른쪽 → 오른쪽 아래 순으로 탐색을 하는 그리디 1, 빵집의 가스관 위쪽부터 차례대로 파이프를 연결할 수 있나? 없나? 를 확인하며 파이프를 만드는 방식의 그리디 2 총 2개의 2그리디 방식을 사용해야 한다.

첫 번째 그리디의 경우 어찌저찌 잘 생각할 수 있겠지만, 두 번째 그리디의 경우에는 생각하기 어려워서.. 매우 오랜 시간이 걸린 문제이다.

로직은 다음과 같다.

• 빵집의 가스관 위쪽 부터 dfs 탐색을 돌며 파이프를 만들 수 있는지 확인한다.
• ( 만들 수 있으면 response 에 +1, 없으면 +0 을 해준다. )

그리디만 알면 생각보다 간단한 문제이나 생각하기 힘들다... 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int n, m;
char arr[10001][501];
int check[10001][501];
int dx[] = { -1,0, 1 };
int dy[] = { 1, 1, 1 };
int _max = 0;
vector<pii> pla;

bool dfs(int x, int y) {
    check[x][y] = 1;
    if (y == m) return true;
    for (int i = 0; i < 3; i++) {
        int cx = x + dx[i];
        int cy = y + dy[i];

        if (cx < 1 || cx > n || cy < 1 || cy > m) continue;
        if (check[cx][cy] || arr[cx][cy] == 'x') continue;

        bool flag = dfs(cx, cy);
        if (flag) return true;
    }
    return false;

}
int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf(" %1c", &arr[i][j]);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += dfs(i, 1);
    }

    cout << res;

    return 0;
}

시간 복잡도가 중요한 문제이다. 일단 제한 시간을 보면 10초인 것을 볼 수 있다.

허나 입력값이 100개인 배열에서 일일이 다 비숍을 넣어가면서 백트래킹을 하게 된다면 O(2^(10*10)) 이 되어 터져버리게 된다.

이를 위해 체스판의 특징을 생각해 흑,백 으로 나눠 로직을 짜보려고 한다. 이렇게 되면 복잡도가 O(2^(5*5)) 가 되어 문제 없이 제한시간을 맞추게 된다. 분할해서 생각한다면 로직은 일반 백트래킹과 다를바 없어 넘어가도록 하겠다.

다만 흑,백으로 나누어 check 배열을 두고 확인하는 로직만 유심히 보면 될것 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int N;
int chess[11][11];
int color[11][11];
int check[11][11];
int dx[] = { -1,1,1,-1 };
int dy[] = { 1,-1,1,-1 };
int max_cnt[2]; 
vector<vector<pii>> zero(2);

bool check_bis(int cx, int cy) {
    for (int i = 0; i < 4; i++) {
        int nx = cx + dx[i];
        int ny = cy + dy[i];

        for (int j = 1; j < N; j++) {
            if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
            if (check[nx][ny]) return false;

            nx += dx[i];
            ny += dy[i];
        }
    }
    return true;
}

void dfs(int n, int cnt, int col) {
    max_cnt[col] = max(cnt, max_cnt[col]);
    if (n + 1 >= zero[col].size()) 
        return;
    
    for (int i = n + 1; i < zero[col].size(); i++) {
        int cx = zero[col][i].first;
        int cy = zero[col][i].second;
        if (color[cx][cy] != col) continue;
        if (check[cx][cy] == 1) continue;
        if (!check_bis(cx, cy)) continue;
        if (chess[cx][cy] == 0) continue;

        check[cx][cy] = 1;
        dfs(i, cnt + 1, col);
        check[cx][cy] = 0;
    }
}

int main() {
    cin >> N;
    int input;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> chess[i][j];
            if ((i + j) % 2 == 0) { 
            // 백색 : 1, 흑색 : 0
                color[i][j] = 0;
                if(chess[i][j]) zero[0].push_back({ i,j });
            }
            else if ((i + j) % 2 == 1) {
                color[i][j] = 1;
                if (chess[i][j]) zero[1].push_back({ i,j });
            }
        }
    }

    dfs(-1, 0, 0);
    dfs(-1, 0, 1);
    
    printf("%d", max_cnt[0] + max_cnt[1]);
    return 0;
}

DP 에 비트마스킹까지 포함시킨 문제이다.

일단 수를 일일이 다 확인해가면서 0부터 9까지 있는지 확인하는 작업은 복잡도 측면에서 몇십배 정도 더 늘어나게 된다. 때문에 이를 위해 비트마스킹 기법을 통한 체킹 로직이 필요하다.

추가로 DP 메모라이징 기법을 통해 이 문제를 비교적 간단하게 풀 수 있다. 처음에만 봤을 때 어렵지 한 번 이해하면 다음에는 쉽지(??!) 않을까 생각하는 문제이다.

다음에 한 번 더 풀어보는 걸로..

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, string> pii;
typedef long long LL;

int N;
int check[10][101][1 << 10];

int stair(int start, int length, int number) {
    if (length == N) 
        return (number == (1 << 10) - 1) ? 1 : 0;
    
    int &result = check[start][length][number];
    if (result != -1)
        return result;

    result = 0;
    if (start - 1 >= 0)
        result += stair(start - 1, length + 1, number | 1 << (start - 1));
    if (start + 1 < 10)
        result += stair(start + 1, length + 1, number | 1 << (start + 1));
    result %= 1000000000;
    return result;
}
int main() {
    cin >> N;

    int res = 0;
    for (int i = 1; i <= 9; i++) {
        memset(check, -1, sizeof(check));
        res += stair(i, 1, 1 << i);
        res %= 1000000000;
    }
    cout << res << endl;

    
    return 0;
}

구현 + DFS 문제였다.

네트워크 개수를 세는 듯한 문제인데 입력받은 U, D, L, R 에 따라 쭉~ 이어주는 동시에 다음 값이 현재 있는 값으로 들어올수도 있는지 확인하는 로직을 구현하면 간단한 문제였다. 다시 로직을 정리하면 다음과 같다.

• 지도 (0,0) 부터 check 되어있지 않으면 dfs 로 해당 지점으로부터 연결되어있는 모든 지도지점을 check
• SAFE ZONE 개수 한개 추가
• 그 후 check 안되어있는 지점으로부터 dfs 처리해서 똑같이 네트워크 check
• SAFE ZONE 한개 추가

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
typedef pair<int, string> pii;
char arr[1001][1001];
int check[1001][1001];
int dx[] = { -1,0,1,0 }; // 위, 왼쪽, 아래, 오른쪽
int dy[] = { 0,-1,0,1 };
int n, m;
char dz[] = { 'D', 'R', 'U','L' };

bool dfs_check(int a, int b, int i) {
    return (a<1 || a > n || b < 1 || b > m) || dz[i] != arr[a][b] || check[a][b] == 1;
}
void dfs(int x, int y) {
    switch (arr[x][y]) {
    case 'D':
        if (x + 1 <= n && check[x + 1][y] == 0) 
            check[x + 1][y] = 1, dfs(x + 1, y);
        for (int i = 0; i < 4; i++) {
            if (i == 2) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1, dfs(cx, cy);
        }
        break;
    case 'L':
        if (y - 1 >= 1 && check[x][y-1] == 0) 
            check[x][y - 1] = 1, dfs(x, y - 1);
        for (int i = 0; i < 4; i++) {
            if (i == 1) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1,  dfs(cx, cy);
        }
        break;
    case 'R':
        if (y + 1 <= m && check[x][y + 1] == 0) 
            check[x][y + 1] = 1, dfs(x, y + 1);
        for (int i = 0; i < 4; i++) {
            if (i == 3) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1, dfs(cx, cy);
        }
        break;
    case 'U':
        if (x - 1 >= 1 && check[x - 1][y] == 0) 
            check[x - 1][y] = 1, dfs(x - 1, y);
        for (int i = 0; i < 4; i++) {
            if (i == 0) continue;
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (dfs_check(cx, cy, i)) continue;
            check[cx][cy] = 1, dfs(cx, cy);
        }
        break;
    }
    return;
}
int main() {
    scanf("%d %d", &n, &m);

    string input;
    for (int i = 1; i <= n; i++) {
        cin >> input;
        for (int j = 1; j <= m; j++) {
            arr[i][j] = input.at(j-1);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (check[i][j] == 1) continue;
            check[i][j] = 1;
            dfs(i, j);
            res += 1;
        }
    }

    printf("%d", res);
    return 0;
}

단순 BFS 를 사용하면 100만 + 300만 정도의 복잡도가 나오게 되어서 전혀 복잡도가 터질 일이 없다.

따라서 BFS 를 따라 로직만 잘 처리해주면 된다. 로직은 다음과 같다.

• 처음 입력된 수와 비어있는 문자열을 queue 에 넣는다.
• 이 후 queue 의 front 를 빼고 3가지 연산 각각을 할 수 잇는지 확인하고 연산이 가능하면 연산된 값을 다시 queue 에 넣고 해당 숫자를 더한 문자열또한 queue 에 넣는다.
• 위의 과정을 1이 나올 떄까지 반복한다.

생각보다 간단한 알고리즘이다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
typedef pair<int, string> pii;
int check[2000001];


void split_str(string s, vector<string>& ans) {
    auto current = s.find(',');
    auto previous = 0;
    while (current != string::npos) {
        string substring = s.substr(previous, current - previous);
        if (substring != "")
            ans.push_back(substring);
        previous = current + 1;
        current = s.find(',', previous);
    }
    ans.push_back(s.substr(previous, current - previous));
    cout << ans.size() - 1 << endl;
    for (auto i : ans)
        cout << i << " ";
    return;
}
int main() {
    int n;
    cin >> n;

    queue<pii> q;
    q.push({ n,"" });

    int cx;
    string ct;
    vector<string> ans;
    ans.push_back(to_string(n));

    if (n == 1) {
        cout << 0 << endl;
        cout << 1;
        return 0;
    }

    while (!q.empty()) {
        cx = q.front().first;
        ct = q.front().second;
        q.pop();
        if (cx == 1) {
            split_str(ct, ans);
            break;
        }
        if (cx % 3 == 0 && check[cx / 3] == 0) {
            check[cx / 3] = 1;
            q.push({ cx / 3, ct + "," + to_string(cx / 3) });
        }
        if (cx % 2 == 0 && check[cx / 2] == 0) {
            check[cx / 2] = 1;
            q.push({ cx / 2, ct + "," + to_string(cx / 2) });
        }
        if (check[cx - 1] == 0) {
            q.push({ cx - 1 , ct + "," + to_string(cx - 1) });
        }
    }

    return 0;
}