• 그리디 알고리즘
• 풀이 어떤 상황이던 심판이 점수를 높게준 K 명의 학생은 수상을 한다는 사실을 알 수 있다. 따라서 심판이 점수를 높게준 K 명을 제외한 주최자가 점수를 높게 준 학생 M 명의 점수를 가장 높게 선정하면 수상하는 학생들의 점수 합을 최대로 얻을 수 있다. 먼저 b 배열을 내림차순으로 정렬하고 앞에서부터 K 명의 점수를 얻는다. 그 후, a 배열을 내림차순으로 정렬하여 앞에서부터 M 명의 점수를 얻되, 이 인원은 이미 선정한 K 명중 포함되지 않아야 한다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
const char en = '\n';
const int INF = (int)1e9 + 7;
const int mod = (int)1e9 + 7;

struct s {
    int a, b;
    bool c;
};

bool cmp_1(s x, s y) {
    if (x.a == y.a) return x.b > y.b;
    return x.a > y.a;
}

bool cmp_2(s x, s y) {
    if (x.b == y.b) return x.a > y.a;
    return x.b > y.b;
}


int main(void) {
    fast;

    int n, m, k; cin >> n >> m >> k;
    vector<s> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i].a >> v[i].b;
        v[i].c = false;
    }

    sort(v.begin(), v.end(), cmp_2);
    ll ans = 0;

    for (int i = 0; i < k; ++i) v[i].c = true;
    sort(v.begin(), v.end(), cmp_1);

    for (int i = 0; m; ++i) {
        if (!v[i].c) v[i].c = true, m--;
    }

    for (int i = 0; i < n; ++i) {
        if (v[i].c) ans += v[i].a;
    }

    cout << ans << en;
    return 0;
}

• 그리디 알고리즘, 애드 혹
• 풀이

1. M과 N이 같을 때, 라즈베리 배열의 모든 칸이 차있으므로 라즈베리를 이동할 수 없습니다. 이 경우엔 a = b가 아닐 시 -1을 출력합니다.
2. 두 참가자의 원하는 라즈베리의 위치가 중복일 시에도 충족되게 나눠줄 수 없습니다. 이 경우엔 -1를 출력합니다.

라즈베리의 원형배열을 일차원 배열처럼 생각합니다. 배정한 라즈베리 파이의 순서를 유지하는 한, 일차원 배열을 계속 확장할 수 있습니다. a,b 배열을 pair로 묶고 b를 기준, 오름차순으로 정렬했습니다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
const char en = '\n';
const int INF = (int)1e9 + 7;
const int mod = (int)1e9 + 7;

bool cmp(pair<ll, ll> a, pair<ll, ll> b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

int main(void) {
    fast;

    int m, n; cin >> m >> n;
    vector<pair<ll, ll>> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].first;
    for (int i = 0; i < n; ++i) cin >> a[i].second;

    if (m == n) {
        for (int i = 0; i < n; ++i) {
            if (a[i].first != a[i].second) {
                cout << -1 << en; return 0;
            }
        }
        cout << 0 << en; return 0;
    }

    sort(a.begin(), a.end(), cmp);
    for (int i = 0; i < n - 1; ++i) {
        if (a[i].second == a[i + 1].second) {
            cout << -1 << en; return 0;
        }
    }

    ll ans = 0, cnt = 0;

    for (int i = 0; i < n - 1; ++i) {
        if (a[i].first > a[i + 1].first) {
            double ce = ceil(((double)a[i].first - (double)a[i + 1].first) / (double)m)*(double)m;
            a[i + 1].first += ce;
        }
    }

    for (int i = 0; i < n; ++i) {
        if (a[i].first + (cnt*m) < a[i].second) {
            cnt += 1;
        }
    }

    for (int i = 0; i < n; ++i) a[i].first += cnt * m;

    if (a.front().first + m <= a.back().first) {
        cout << -1 << en; return 0;
    }
    for (int i = 0; i < n; ++i) ans += a[i].first - a[i].second;
    cout << ans << en;

    return 0;
}

• 예제에 관한 풀이 그림 첨부 순서대로 입력 예제 1,2 입니다.

• 라즈베리 배열은 원래 원형 배열이므로, 정렬된 a 배열의 마지막 조각은 처음 a 조각 + M 보다 크거나 같아야 합니다. ( if(a.front().first + m <= a.back().first 부분입니다.)

• 참가자에게 배정한 파이 조각 위치는 참가자가 원하는 파이 조각의 번호보다 커야합니다.

• 올해 진행된 UCPC 문제들을 몇 문제 풀어봤습니다. 다들 난이도가 상당히 어려웠고, 이 문제는 거진 3일 정도 생각하여 푼 문제였습니다.

• 문자열, 그리디 알고리즘

• 풀이 문자열 S 에 대하여 반복해서 T를 찾으면 시간 초과가 날 수 있다고 생각했다. 앞쪽 문자열이 이미 나왔는지를 확인한다. 만약 s[i]가 t[j]와 같을 시 t[j] 이전 문자들이 몇 번 나왔는지 확인한다. 이전 문자들이 더 적게 나왔을 경우 추가하지 않고 많이 나왔을 경우만 추가한다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long 
#define pii pair<long, long>

string s, t;
vector<int> A;
int cnt = 0;

bool check_prev(int N) {
    for (int i = 0; i < N; ++i) {
        if (!A[i] or A[i] <= A[N]) return false;
    }
    return true;
}

bool complete() {
    for (int i = 0; i < A.size(); ++i) {
        if (!A[i]) return false;
    }
    return true;
}

void del() {
    for (int i = 0; i < A.size(); ++i) A[i]--;
}

int main(void) {
    fast;

    cin >> s >> t;
    A.resize(t.size());
    for (int i = 0; i < s.size(); ++i) {
        for (int j = 0; j < t.size(); ++j) {
            if (s[i] == t[j]) {
                if (check_prev(j)) {
                    A[j]++;
                    if (complete()) {
                        del(); cnt++;
                    }
                }
            }
        }
    }
    cout << cnt;
}

• check_prev 함수 중 A[i] <= A[N] 부분을 추가해주셔야 합니다. 재미있게 푼 문제입니다!

• 자료 구조, 큐, 시뮬레이션

• 풀이 기재된 섞는 순서에 맞춰 left_side queue, right_side queue 에 분배해 놓는다. 입력은 총 카드 수인 27 합을 맞출 때까지 받는다. 오른쪽 한번 왼쪽 한번 반복하여 left_side, right_side에서 카드를 메인 queue로 보내 합친다. 위 로직을 반복한다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)

int N;
queue<int> ls, rs, ret;

int main(void){
    fast;
    cin>>N;
    ret.push(-1);
    for(int i=0;i<26;++i) ret.push(1);
    while(N--){
        int cnt=0;
        for(int i=0;i<13;++i) {
            ls.push(ret.front()); ret.pop();
        }
        for(int i=0;i<14;++i){
            rs.push(ret.front()); ret.pop();
        }
        bool flag=true;
        while(cnt<27){
            int card; cin>>card;
            cnt+=card;
            for(int i=0;i<card;++i){
                if(flag){
                    ret.push(rs.front()); rs.pop();
                } else{
                    ret.push(ls.front()); ls.pop();
                }
            }
            flag=!flag;
        }
    }
    for(int i=1;i<=27;++i){
        int cur=ret.front(); ret.pop();
        if(cur==-1){
            cout<<i; return 0;
        }
    }
}

• 자료구조 - 큐와 구현력을 물어보는 문제

• 자료 구조, 분리 집합

• 풀이 연결되어 있는 건물들을 같은 집합에 포함 시킨다. 그 후 다른 집합에 있는 건물일 시 (check 함수), res를 더하여 마지막에 출력한다.

• 코드

  #include <bits/stdc++.h>
  using namespace std;
  #define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
  

const int MAX = 101010; int N, M, res=0; int par[MAX];

void init(int num){ for(int i=0;i<num;i++) par[i]=i; }

int find(int x){ if(x==par[x]) return x; return par[x]=find(par[x]); }

void Union(int x, int y){ x=find(x); y=find(y); if(x<y) par[y]=x; else par[x]=y; }

bool check(int x, int y){ x=find(x); y=find(y); if(x==y) return true; return false; }

int main(void){ fast; cin>>N>>M; init(N); for(int i=0;i<M;++i){ int s,e; cin>>s>>e; Union(s,e); } vector table(N); for(int i=0;i<N;++i) cin>>table[i]; for(int i=0;i<N-1;++i){ if(!check(table[i], table[i+1])) res++; } cout<<res; }

• 그리디 알고리즘

• 풀이 거스름돈 문제와 비슷한 로직으로 해결했다. 30초, 60초 이하인 부분만 예외로 처리했다.

• 코드

  #include <bits/stdc++.h>
  using namespace std;
  #define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
  

string tt; int M,S;

int main(void){ fast; cin>>tt; M=stoi(tt.substr(0,2)); S=stoi(tt.substr(3,2)); S+=M*60; if(!S){ cout<<0; return 0; } if(S<30){ cout<<(S/10)+1; return 0; } if(S<60){ cout<<((S-30)/10)+1; return 0; } int A=S; int ss, sm=1; S-=30; ss=1; ss+=S/600; S%=600; ss+=S/60; S%=60; ss+=S/30; S%=30; ss+=S/10;

sm+=A/600; A%=600;
sm+=A/60; A%=60;
sm+=A/30; A%=30;
sm+=A/10;
cout<<min(ss,sm);

}

• 브루트포스 알고리즘, 구현

• 풀이 ㄷ자를 만들 수 있는 모든 경우들을 확인했다.

• 코드

  #include <bits/stdc++.h>
  using namespace std;
  #define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
  #define ll long long
  #define vc vector
  #define vi vector<int>
  #define vs vector<string>
  #define pb push_back
  #define mp make_pair
  #define pii pair<int,int>
  #define pll pair<ll,ll>
  

int n, m, a, b, mv=(int)1e9; bool A[22][22]; bool visited[22][22];

void ch3(int x, int y) { int cnt = 0; memset(visited, false, sizeof(visited)); for (int i = y; i < y + 3; ++i) { if (!A[x][i]) cnt += a; visited[x][i] = true; } if (!A[x + 1][y]) cnt += a; visited[x + 1][y] = true; for (int i = y; i < y + 3; ++i) { if (!A[x + 2][i]) cnt += a; visited[x + 2][i] = true; } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!visited[i][j] and A[i][j]) cnt += b; } } mv = min(mv, cnt);
}

void ch6(int x, int y) { int cnt = 0; memset(visited, false, sizeof(visited)); for (int i = y; i < y + 6; ++i) { if (!A[x][i]) cnt += a; visited[x][i] = true; } for (int i = y; i < y + 6; ++i) { if (!A[x+1][i]) cnt += a; visited[x+1][i] = true; } for (int i = y; i < y + 2; ++i) { if (!A[x + 2][i]) cnt += a; visited[x + 2][i] = true; } for (int i = y; i < y + 2; ++i) { if (!A[x + 3][i]) cnt += a; visited[x + 3][i] = true; } for (int i = y; i < y + 6; ++i) { if (!A[x + 4][i]) cnt += a; visited[x + 4][i] = true; } for (int i = y; i < y + 6; ++i) { if (!A[x + 5][i]) cnt += a; visited[x + 5][i] = true; } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!visited[i][j] and A[i][j]) cnt += b; } } mv = min(mv, cnt); }

void ch9(int x, int y) { int cnt = 0; memset(visited, false, sizeof(visited)); for (int i = y; i < y + 9; ++i) { if (!A[x][i]) cnt += a; visited[x][i] = true; } for (int i = y; i < y + 9; ++i) { if (!A[x+1][i]) cnt += a; visited[x+1][i] = true; } for (int i = y; i < y + 9; ++i) { if (!A[x+2][i]) cnt += a; visited[x+2][i] = true; } for (int i = y; i < y + 3; ++i) { if (!A[x + 3][i]) cnt += a; visited[x + 3][i] = true; } for (int i = y; i < y + 3; ++i) { if (!A[x + 4][i]) cnt += a; visited[x + 4][i] = true; } for (int i = y; i < y + 3; ++i) { if (!A[x + 5][i]) cnt += a; visited[x + 5][i] = true; } for (int i = y; i < y + 9; ++i) { if (!A[x + 6][i]) cnt += a; visited[x + 6][i] = true; } for (int i = y; i < y + 9; ++i) { if (!A[x + 7][i]) cnt += a; visited[x + 7][i] = true; } for (int i = y; i < y + 9; ++i) { if (!A[x + 8][i]) cnt += a; visited[x + 8][i] = true; } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!visited[i][j] and A[i][j]) cnt += b; } } mv = min(mv, cnt); }

void ch12(int x, int y) { int cnt = 0; memset(visited, false, sizeof(visited)); for (int i = y; i < y + 12; ++i) { if (!A[x][i]) cnt += a; visited[x][i] = true; } for (int i = y; i < y + 12; ++i) { if (!A[x+1][i]) cnt += a; visited[x+1][i] = true; } for (int i = y; i < y + 12; ++i) { if (!A[x+2][i]) cnt += a; visited[x+2][i] = true; } for (int i = y; i < y + 12; ++i) { if (!A[x+3][i]) cnt += a; visited[x+3][i] = true; } for (int i = y; i < y + 4; ++i) { if (!A[x+4][i]) cnt += a; visited[x+4][i] = true; } for (int i = y; i < y + 4; ++i) { if (!A[x+5][i]) cnt += a; visited[x+5][i] = true; } for (int i = y; i < y + 4; ++i) { if (!A[x+6][i]) cnt += a; visited[x+6][i] = true; } for (int i = y; i < y + 4; ++i) { if (!A[x+7][i]) cnt += a; visited[x+7][i] = true; } for (int i = y; i < y + 12; ++i) { if (!A[x+8][i]) cnt += a; visited[x+8][i] = true; } for (int i = y; i < y + 12; ++i) { if (!A[x+9][i]) cnt += a; visited[x+9][i] = true; } for (int i = y; i < y + 12; ++i) { if (!A[x+10][i]) cnt += a; visited[x+10][i] = true; } for (int i = y; i < y + 12; ++i) { if (!A[x+11][i]) cnt += a; visited[x+11][i] = true; } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!visited[i][j] and A[i][j]) cnt += b; } } mv = min(mv, cnt); }

void ch15(int x, int y) { int cnt = 0; memset(visited, false, sizeof(visited)); for (int i = y; i < y + 15; ++i) { if (!A[x][i]) cnt += a; visited[x][i] = true; } for (int i = y; i < y + 15; ++i) { if (!A[x+1][i]) cnt += a; visited[x+1][i] = true; } for (int i = y; i < y + 15; ++i) { if (!A[x+2][i]) cnt += a; visited[x+2][i] = true; } for (int i = y; i < y + 15; ++i) { if (!A[x+3][i]) cnt += a; visited[x+3][i] = true; } for (int i = y; i < y + 15; ++i) { if (!A[x+4][i]) cnt += a; visited[x+4][i] = true; } for (int i = y; i < y + 5; ++i) { if (!A[x+5][i]) cnt += a; visited[x+5][i] = true; } for (int i = y; i < y + 5; ++i) { if (!A[x+6][i]) cnt += a; visited[x+6][i] = true; } for (int i = y; i < y + 5; ++i) { if (!A[x+7][i]) cnt += a; visited[x+7][i] = true; } for (int i = y; i < y + 5; ++i) { if (!A[x+8][i]) cnt += a; visited[x+8][i] = true; } for (int i = y; i < y + 5; ++i) { if (!A[x+9][i]) cnt += a; visited[x+9][i] = true; } for (int i = y; i < y + 15; ++i) { if (!A[x+10][i]) cnt += a; visited[x+10][i] = true; } for (int i = y; i < y + 15; ++i) { if (!A[x+11][i]) cnt += a; visited[x+11][i] = true; } for (int i = y; i < y + 15; ++i) { if (!A[x+12][i]) cnt += a; visited[x+12][i] = true; } for (int i = y; i < y + 15; ++i) { if (!A[x+13][i]) cnt += a; visited[x+13][i] = true; } for (int i = y; i < y + 15; ++i) { if (!A[x+14][i]) cnt += a; visited[x+14][i] = true; }

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        if (!visited[i][j] and A[i][j]) cnt += b;
    }
}
mv = min(mv, cnt);

}

void ch18(int x, int y) { int cnt = 0; memset(visited, false, sizeof(visited)); for (int i = y; i < y + 18; ++i) { if (!A[x][i]) cnt += a; visited[x][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+1][i]) cnt += a; visited[x+1][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+2][i]) cnt += a; visited[x+2][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+3][i]) cnt += a; visited[x+3][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+4][i]) cnt += a; visited[x+4][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+5][i]) cnt += a; visited[x+5][i] = true; } for (int i = y; i < y + 6; ++i) { if (!A[x+6][i]) cnt += a; visited[x+6][i] = true; } for (int i = y; i < y + 6; ++i) { if (!A[x+7][i]) cnt += a; visited[x+7][i] = true; } for (int i = y; i < y + 6; ++i) { if (!A[x+8][i]) cnt += a; visited[x+8][i] = true; } for (int i = y; i < y + 6; ++i) { if (!A[x+9][i]) cnt += a; visited[x+9][i] = true; } for (int i = y; i < y + 6; ++i) { if (!A[x+10][i]) cnt += a; visited[x+10][i] = true; } for (int i = y; i < y + 6; ++i) { if (!A[x+11][i]) cnt += a; visited[x+11][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+12][i]) cnt += a; visited[x+12][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+13][i]) cnt += a; visited[x+13][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+14][i]) cnt += a; visited[x+14][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+15][i]) cnt += a; visited[x+15][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+16][i]) cnt += a; visited[x+16][i] = true; } for (int i = y; i < y + 18; ++i) { if (!A[x+17][i]) cnt += a; visited[x+17][i] = true; } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!visited[i][j] and A[i][j]) cnt += b; } }

mv = min(mv, cnt);

}

int main(void) { fast; cin >> n >> m >> a >> b; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char c; cin >> c; if (c == '#') A[i][j] = true; else A[i][j] = false; } } int u = min(n, m);

if (u >= 18) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i + 2 < n and j + 2 < m) ch3(i, j);
            if (i + 5 < n and j + 5 < m) ch6(i, j);
            if (i + 8 < n and j + 8 < m) ch9(i, j);
            if (i + 11 < n and j + 11 < m) ch12(i, j);
            if (i + 14 < n and j + 14 < m) ch15(i, j);
            if (i + 17 < n and j + 17 < m) ch18(i, j);
        }
    }
}
else if (u >= 15) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i + 2 < n and j + 2 < m) ch3(i, j);
            if (i + 5 < n and j + 5 < m) ch6(i, j);
            if (i + 8 < n and j + 8 < m) ch9(i, j);
            if (i + 11 < n and j + 11 < m) ch12(i, j);
            if (i + 14 < n and j + 14 < m) ch15(i, j);
        }
    }
}
else if (u >= 12) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i + 2 < n and j + 2 < m) ch3(i, j);
            if (i + 5 < n and j + 5 < m) ch6(i, j);
            if (i + 8 < n and j + 8 < m) ch9(i, j);
            if (i + 11 < n and j + 11 < m) ch12(i, j);
        }
    }
}
else if (u >= 9) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i + 2 < n and j + 2 < m) ch3(i, j);
            if (i + 5 < n and j + 5 < m) ch6(i, j);
            if (i + 8 < n and j + 8 < m) ch9(i, j);
        }
    }
}
else if (u >= 6) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i + 2 < n and j + 2 < m) ch3(i, j);
            if (i + 5 < n and j + 5 < m) ch6(i, j);
        }
    }
}
else if (u >= 3) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if(i+2<n and j+2 < m) ch3(i, j);
        }
    }
}        
cout << mv;

}

```

• 딱 떠오르는 풀이가 없어서 모든 경우의 수들을 확인했습니다....

• 그래프 이론, 애드 혹, 많은 조건 분기

• 풀이 각각 I, N, U을 그래프의 정점으로 생각하여 연결되어 있는지를 확인한다. 다 연결되있다면 모든 값들의 합이 답이고 그 외는 간선들의 합을 비교하여 찾는다.

• 코드

  #include <bits/stdc++.h>
  using namespace std;
  #define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
  #define ll long long
  

int N; int ii=0,nn=0,uu=0; int in=0, iu=0,nu=0; int ctin=0, ctiu=0, ctnu=0;

int main(void){ fast; cin>>N; for(int i=0;i<N;++i) { string s; int n; cin>>s>>n; if(s[0]==s[1]){ if(s[0]=='I') ii+=n; else if(s[0]=='N') nn+=n; else uu+=n; } else{ if((s[0]=='I' and s[1]=='N') or s[0]=='N' and s[1]=='I') { in+=n; ctin++; } if((s[0]=='I' and s[1]=='U') or s[0]=='U' and s[1]=='I') { iu+=n; ctiu++; } if((s[0]=='N' and s[1]=='U') or s[0]=='U' and s[1]=='N') { nu+=n; ctnu++; } } } if((ctin and ctiu and ctnu) or (ctin and ctiu and !ctnu) or (ctin and !ctiu and ctnu) or (!ctin and ctiu and ctnu)){ cout<<ii+nn+uu+in+iu+nu; return 0; }

if(ctin and !ctiu and !ctnu) {
    cout<<max(uu,ii+nn+in); return 0;
}

if(!ctin and ctiu and !ctnu) {
    cout<<max(nn,ii+uu+iu); return 0;
}

if(!ctin and !ctiu and ctnu) {
    cout<<max(ii,nn+uu+nu); return 0;
}
if(!ctin and !ctiu and !ctnu){
    cout<<max(ii,max(nn,uu)); return 0;
}

} ```

• 그리디 알고리즘

• 풀이 마트료시카를 가장 길게 만드는 것이 수익을 최대로 얻을 수 있으므로 가장 작은 값부터 최대한 긴 마트료시카를 얻는 것을 반복한다.

• 코드

  #include <bits/stdc++.h>
  using namespace std;
  #define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
  #define ll long long
  

ll N,ans=0; vector v; ll m[202020];

int main(void){ fast; cin>>N; memset(m,0,sizeof(m)); v.resize(N); for(int i=0;i<N;++i) { cin>>v[i]; m[v[i]]++; }

sort(v.begin(),v.end());
ll Q,cnt;
for(int i=0;i<N;++i){
    if(m[v[i]]){
        m[v[i]]--;
        Q=v[i], cnt=1;
        for(int j=v[i]+1;;++j){
            if(m[j]){
                Q=j; m[j]--; cnt++;
            }
            else{
                ans+=Q*cnt;
                break;
            }
        }
    }
}
cout<<ans;

}

• 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐

• 풀이

1. 먼저 충전해야할 전자기기들을 충전 시간이 긴 순으로 정렬한다.
2. priority queue 구조인 사용 가능한 콘센트에 전부 충전시킨다.
3. 먼저 끝나는 콘센트부터 다음으로 충전 시간이 긴 기기를 충전시킨다. 즉 priority queue의 top부터 갱신한다.
4. 가장 오래 충전하는 콘센트의 시간을 출력한다.

• 코드

  #include <bits/stdc++.h>
  using namespace std;
  #define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
  #define ll long long
  

int N,M,ans=0,idx=0; priority_queue<int,vector,greater> qq;

int main(void){ fast; cin>>N>>M; vector v(N); for(int i=0;i<N;++i) cin>>v[i]; sort(v.begin(),v.end(), greater());

if(M==1){
    for(int i=0;i<N;++i){
        ans+=v[i];
    }
    cout<<ans; return 0;
}

if(N<M){
    int mv=0;
    for(int i=0;i<N;++i) mv=max(v[i],mv);
    cout<<mv; return 0;
}

for(int i=0;i<M;++i) qq.push(v[i]);
idx+=M;

while(idx<N){
    int ns=qq.top(); qq.pop();
    while(ns<=qq.top() and idx<N){
        ns+=v[idx]; idx++;
    }
    qq.push(ns);
}
for(int i=0;i<M-1;++i) qq.pop();
cout<<qq.top();

}

```

• M이 1일 때와 N보다 클 때는 예외처리하였다. ( M==1일 시 모든 충전기기의 합, M>N일 시 가장 충전 시간이 긴 전자기기의 값이 정답이다. )

• 브루트포스 알고리즘

• 풀이 올바른 수식을 찾아 반복문을 수행한다. 항상 두 자릿수에 맞게 표현해야 한다는 조건으로 출력한다.

• 코드

  #include <bits/stdc++.h>
  using namespace std;
  #define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
  #define ll long long
  

int main(void){ fast; int N; cin>>N; int a[10]={6,2,5,5,4,5,6,3,7,6};

N-=4;
for(int i=0;i<10;++i){
    for(int j=0;j<10;++j){
        for(int l=0;l<10;++l){
            for(int k=0;k<10;++k){
                for(int h=0;h<10;++h){
                    for(int g=0;g<10;++g){
                        if((a[i]+a[j]+a[l]+a[k]+a[h]+a[g]==N) and (i*10+j+l*10+k==h*10+g)) {
                            cout<<i<<j<<'+'<<l<<k<<'='<<h<<g; return 0;
                        }
                    }
                }
            }
        }
    }
}
cout<<"impossible";

} ```

• 구현, 문자열

• 풀이 좌우 방향으로 포개어 접으므로 올바른 위치로 물감을 복사시켜주면 된다.

• 코드

  #include <bits/stdc++.h>
  using namespace std;
  #define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
  #define ll long long
  

int N,M; char m[55][55];

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

for(int i=0;i<N;++i){
    for(int j=0;j<M;++j){
        if(m[i][j]!='.'){
            m[i][M-j-1]=m[i][j];
        }
    }
}

for(int i=0;i<N;++i){
    for(int j=0;j<M;++j){
        cout<<m[i][j];
    }
    cout<<"\n";
}

}

• 다이나믹 프로그래밍

• 풀이

1. dp 배열과 정답 배열 두개를 만들고, dp 배열에서 오른쪽과 아래로 이동했을 때, 숫자가 N보다 크지 않으면 정답 배열에 경우의 수 합을 넣는다. (arr[i+d[i][j]][j]+=ans[i][j])
2. 마지막 (N,N)칸에서 한번 더 경우의 수들을 더해주지 않도록 한다. if .... !(i==N and j==N)
3. 값이 int보다 커질 수 있으므로 long long 자료형을 사용한다.

• 코드

  #include <bits/stdc++.h>
  using namespace std;
  #define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
  #define ll long long
  #define vc vector
  #define vi vector<int>
  #define vs vector<string>
  #define pb push_back
  #define mp make_pair
  #define pii pair<int,int>
  #define pll pair<ll,ll>
  

ll N; ll d[101][101], ans[101][101];

int main(void){ fast; cin>>N; for(int i=1;i<=N;++i){ for(int j=1;j<=N;++j){ cin>>d[i][j]; } } memset(ans,0,sizeof(ans)); ans[1][1]=1; for(int i=1;i<=N;++i){ for(int j=1;j<=N;++j){ if(i+d[i][j]<=N and ans[i][j] and !(i==N and j==N)) ans[i+d[i][j]][j]+=ans[i][j]; if(j+d[i][j]<=N and ans[i][j] and !(i==N and j==N)) ans[i][j+d[i][j]]+=ans[i][j]; } } cout<<ans[N][N]; }

• 너비 우선 탐색
• 풀이 세 가지 방법(한 칸 뒤로, 한 칸 앞으로, 현재 칸의 두 배인 위치로)으로 이동할 수 있습니다. pop할 때 visited를 check해야 다른 경우들을 고려할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

// 12851 숨바꼭질2

int N,K,ans,ac=0;
bool visited[101010];
queue<pii> q;

void bfs(int x){
    visited[x]=true;
    q.push({x,0});
    while(!q.empty()){
        int x=q.front().first, cnt=q.front().second;
        q.pop();
        visited[x]=true;
        if(x==K and ac){
            if(cnt==ans) ac++;
        }
        if(x==K and !ac){
            ans=cnt; ac++;
        }


        for(int i=0;i<3;++i){
            if(i==0) {
                int nx=x-1;
                if(nx>=0 and !visited[nx]){
                    q.push({nx,cnt+1});
                }
            }
            else if(i==1) {
                int nx=x+1;
                if(nx<101010 and !visited[nx]){
                    q.push({nx,cnt+1});
                }
            }
            else {
                int nx=x*2;
                if(nx<101010 and !visited[nx]){
                    q.push({nx,cnt+1});
                }
            }


        }
    }
    cout<<ans<<"\n"<<ac;
}

int main(void){
    fast;
    memset(visited,false,sizeof(visited));
    cin>>N>>K;
    bfs(N);
}

• 너비 우선 탐색
• 풀이 특정 횟수 만큼 장기 '마' 처럼 점프할 수 있는 BFS문제입니다. 3차원 방문 배열을 사용하여 점프하는 경우와 인접한 곳으로 이동하는 경우를 둘다 살펴봐야 합니다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
using ll = long long;

// 1600 말이 되고픈 원숭이

int K, W, H;
int m[202][202];
bool visited[202][202][31];
int d[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int dh[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1} };
queue<pair<pii, pii> >q;

void bfs(int x, int y, int hc, int cnt) { // hc : K 남은 횟수, cnt : 이동 거리 카운트
    visited[x][y][hc] = true;
    q.push({ {x,y},{hc,cnt} });
    while (!q.empty()) {
        int x = q.front().first.first, y = q.front().first.second, hc = q.front().second.first, cnt = q.front().second.second;
        q.pop();
        if (x == H - 1 and y == W - 1) {
            cout << cnt; return;
        }

        if (hc>0) {
            for (int j = 0; j < 8; ++j) {
                int nx = x + dh[j][0], ny = y + dh[j][1];
                if (nx < 0 or nx >= H or ny < 0 or ny >= W) continue;
                if (!visited[nx][ny][hc-1] and !m[nx][ny]) {
                    visited[nx][ny][hc-1] = true;
                    q.push({ {nx,ny},{hc - 1,cnt + 1} });
                }
            }
        }

        for (int i = 0; i < 4; ++i) {
            int nx = x + d[i][0], ny = y + d[i][1];
            if (nx < 0 or nx >= H or ny < 0 or ny >= W) continue;
            if (!visited[nx][ny][hc] and !m[nx][ny]) {
                visited[nx][ny][hc] = true;
                q.push({ {nx,ny},{hc,cnt + 1} });
            }
        }
    }
    cout << -1;
}



int main(void) {
    fast;
    cin >> K >> W >> H;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> m[i][j];
        }
    }
    bfs(0, 0, K, 0);    
}

• W, H를 반대로 생각해서 헷갈렸던 문제입니다.

• 너비 우선 탐색
• 풀이 기본 BFS 풀이를 적용했다. 이동할 수 있는 곳은 방문하지 않았던 up stair, down stair 두 군데이며, queue 에 넣기 전에 방문을 한 곳인지, 1층보다 더 내려 가는지 최고층보다 높이 올라가는지를 확인하여 push 했다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
using ll = long long;

// 5014 스타트링크

int F, S, G, U, D; // F:총 층수, S:현재 위치, G: 스타트링크 위치, U: 위로가기 버튼 누를시, D: 내려가기 버튼 누를 시
bool visited[1010101];
vi v;
queue<pii> q;

void bfs(int cur, int cnt) {

    visited[cur] = true;
    q.push({ cur,cnt });

    while (!q.empty()) {
        int cur = q.front().first, cnt = q.front().second; q.pop();
        if (cur == G) {
            cout << cnt; return;
        }
        for (int i = 0; i < 2; ++i) {
            int nx = cur + v[i];
            if (nx <= F and nx >= 1 and !visited[nx]) {
                visited[nx] = true;
                q.push({ nx,cnt + 1 });
            }
        }
    }
    cout << "use the stairs";
}

int main(void) {
    fast;
    cin >> F >> S >> G >> U >> D;
    v.pb(U); v.pb(D * (-1));
    bfs(S, 0);
}

-

• 구현, 수학
• 풀이 단순 구현 문제

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

// 23739 벼락치기

int N,ans=0,sum=0;
vi v;

int main(void){
    fast;
    cin>>N;
    v.resize(N);
    for(int i=0;i<N;++i) {
        cin>>v[i];
        if((v[i]+1)/2<=30-sum) ans++;
        sum+=v[i];
        if(sum>=30) sum=0;
    }
    cout<<ans;
}

• 구현, 문자열

• 풀이 매칭되는 문자열로 바꿔주면 바꿔주면 된다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

// 23738 Ресторан

int main(void){
    fast;
    string s, ans=""; cin>>s;
    for(int i=0;i<s.size();++i){
        if(s[i]=='A') ans+="a";
        else if(s[i]=='B') ans+="v";
        else if(s[i]=='E') ans+="ye";
        else if(s[i]=='K') ans+="k";
        else if(s[i]=='M') ans+="m";
        else if(s[i]=='H') ans+="n";
        else if(s[i]=='O') ans+="o";
        else if(s[i]=='P') ans+="r";
        else if(s[i]=='C') ans+="s";
        else if(s[i]=='T') ans+="t";
        else if(s[i]=='Y') ans+="u";
        else ans+="h";
    }
    cout<<ans;
}

• 그리디 알고리즘, 정렬
• 풀이

1. 점수를 받은 벡터를 정렬하고, 음수인 점수를 가진 인원들은 팀을 각각 따로 나누고 (음수 점수들의 합 : am), 양수인 점수를 가진 인원들은 하나의 팀 (ap)으로 묶는다.
2. 음수인 점수를 가진 팀들 중에서 점수가 가장 큰 값을 가진 팀을 한 팀씩 ap 팀으로 보내면서 모든 플레이어의 점수의 합을 갱신한다.

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

// 23742 Player-based Team Distribution 

ll N, ans = 0, cnt = 0, idx=-1, am = 0, ap = 0;
vi v;

int main(void) {
    fast;
    cin >> N;
    v.resize(N);
    for (int i = 0; i < N; ++i) cin >> v[i];
    sort(v.begin(), v.end());
    for (int i = 0; i < N; ++i) {
        if (v[i] < 0) am += v[i];
        if (v[i] >= 0 and idx == -1) idx = i;
        if (v[i] >= 0) ap += v[i];
    }
    ans = am + (N - idx) * ap;
    for (int i = idx - 1; i >= 0; --i) {
        am -= v[i]; ap += v[i];
        ans = max(ans, am + (N - i) * ap);
    }

    cout << ans;
}

• 합친 점수의 합들의 범위를 생각해 long long 자료형으로 선언하여 정답을 받았습니다.

• 풀이 주어진 N개의 노선들을 시작 구간을 기준으로 정렬 후, 스위핑 기법을 사용 가장 오른쪽 버스 노선의 e가 s보다 작다면 새로운 버스 노선을 만들어야 하고 크다면 e와 min_val(요금)을 변경

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define vc vector
#define vi vector<int>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

// 23740 버스 노선 개편하기

int N, cnt = 1;
vc<pair<pii, int>> v, ans;

int main(void) {
    fast;
    cin >> N;
    v.resize(N);
    for (int i = 0; i < N; ++i) cin >> v[i].first.first >> v[i].first.second >> v[i].second;
    sort(v.begin(), v.end());

    int s = v[0].first.first, e = v[0].first.second, mv = v[0].second;
    for (int i = 1; i < N; ++i) {
        if (v[i].first.first > e) {
            cnt++;
            ans.pb({ {s,e},mv });
            s = v[i].first.first, e = v[i].first.second, mv = v[i].second;
        }
        else {
            e = max(e, v[i].first.second);
            mv = min(mv, v[i].second);
        }
    }
    ans.pb({ {s,e},mv });
    cout << cnt << "\n";
    for (auto i : ans) cout << i.first.first << ' ' << i.first.second << ' ' << i.second << "\n";
}

• 스위핑 기법을 통해 쉽게 풀 수 있는 문제