hckim

풀이

• 배열 a 를 함수로 생각해서 세번 적용

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N = 10;
    vector<int> a(N);
    for (auto& e: a) {
        cin >> e;
    }

    cout << a[a[a[0]]] << '\n';
}

풀이

• 멀티셋에 가진 누들 길이 다 넣고 플랜 진행하면서 없으면 No

코드

• 시간복잡도: $O(NlogN + MlogN)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N, M;
    cin >> N >> M;
    vector<int> a(N), b(M);
    multiset<int> s;
    for (auto& e: a) {
        cin >> e;
        s.insert(e);
    }
    for (auto& e: b) {
        cin >> e;
        auto it = s.find(e);
        if (it == s.end()) {
            cout << "No\n";
            return 0;
        }

        s.erase(it);
    }

    cout << "Yes\n";

}

풀이

• 한 칸에 대해서, 그 칸을 시작으로 8방향에 대해서, 6칸 중 # 이 네칸이상이면 그 칸에서 그 방향으로 최대 2번 칠해서 6개 연속만들기 가능

코드

• 시간복잡도: $O(N^2*8*6)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N;
    cin >> N;

    vector<string> a(N);
    for (auto& e: a) {
        cin >> e;
    }

    int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

    auto check = [&](int r, int c) {
        for (int dir = 0; dir < 8; dir++) {
            int rr = r + dr[dir] * 5;
            int cc = c + dc[dir] * 5;
            if (rr < 0 || rr >= N || cc < 0 || cc >= N) continue;
            int cnt = 0;
            for (int k = 0; k < 6; ++k) {
                int nr = r + dr[dir] * k;
                int nc = c + dc[dir] * k;
                cnt += a[nr][nc] == '.';
            }
            if (cnt <= 2) return true;
        }
        return false;
    };
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (check(i, j)) {
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
}

풀이

• 멀티셋으로 관리
• 1 쿼리 
  • 멀티셋에 삽입
• 2 쿼리
  • lower bound 부터 최대 k 번 뒤로 iterate
• 3 쿼리
  • upper bound 의 prev 부터 최대 k 번 앞으로 iterate 

코드

• 시간복잡도: $O(QlogQk)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int Q;
    cin >> Q;

    multiset<long long> a;

    while (Q--) {
        long long q, x, k;
        cin >> q >> x;
        if (q == 1) {
            a.insert(x);
        } else if (q == 2) {
            cin >> k; 
            auto it = a.upper_bound(x);
            if (it == a.begin()) {
                cout << "-1\n";
                continue;
            }
            it = prev(it);
            while (true) {
                if (--k == 0) {
                    cout << *it << '\n';
                    break;
                }
                if (it == a.begin()) break;
                it = prev(it);
            }
            if (k) {
                cout << "-1\n";
                continue;
            }
        } else {
            cin >> k;
            auto it = a.lower_bound(x);
            if (it == a.end()) {
                cout << "-1\n";
                continue;
            }
            while (true) {
                if (it == a.end()) break;
                if (--k == 0) {
                    cout << *it << '\n';
                    break;
                }
                it = next(it);
            }
            if (k) {
                cout << "-1\n";
                continue;
            }
        }
    }
}

풀이

• ans[i]: i 번후 접시위 사탕 수라고 정의하면
• $ans[i] % N == ans[i + p] % N$ 인 $1 <= p <= N$ 이 존재
• $ans[i] % N$ 은 그 때 $p$ 주기를 갖는다, 즉 더해지는 수가 $p$ 주기를 가지고 반복된다

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    long long N, K;
    cin >> N >> K;
    vector<long long> a(N);
    for (auto& e: a) {
        cin >> e;
    }

    vector<long long> v(N + 1, 0), v2(N + 1, 0), cnt(N, 0);
    cnt[0] = 1;

    long long idx = -1, p = -1;
    for (int i = 1; i <= N; ++i) {
        v[i] = v[i - 1] + a[v2[i - 1]];
        v2[i] = v[i] % N;
        
        if (++cnt[v2[i]] == 2) {
            auto it = find(v2.begin(), v2.begin() + i, v2[i]);
            idx = it - v2.begin();
            p = i - idx;
            break;
        }
    }

    long long answer = 0;
    if (K <= idx) {
        answer = v[K];
    } else {
        K -= idx;
        answer += v[idx] + (K / p) * (v[idx + p] - v[idx]);
        K %= p;
        for (int i = 0; i < K; ++i) {
            answer += a[v2[idx + i]];
        }
    }

    assert(p >= 1);

    cout << answer << '\n';
}

풀이

• 작은 수 + 1 == 큰 수 임을 체크한다.
• 작은 수 1 , 큰 수 10 케이스에 주의

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int a, b;
    cin >> a >> b;

    if (a > b) swap(a, b);

    if (a == 1 && b == 10) {
        cout << "Yes\n";
    } else if (a + 1 == b) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

풀이

• distinct 원소 개수 구하기
• set 에 insert

코드

• 시간복잡도: $O(NlogN)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N;
    cin >> N;
    set<int> s;
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        s.insert(num);
    }
    cout << s.size() << '\n';
}

풀이

• $dp[i][j]: i$번 점프후 $j$위치에 있는 것이 가능하면 $1$ 아니면 $0$
• $dp[i][j] = 1$ 이면 $dp[i + 1][j + a[i + 1]] = dp[i + 1][j + b[i + 1]] = 1$

코드

• 시간복잡도: $O(NX)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N, X;
    cin >> N >> X;

    vector<vector<long long> > dp(N, vector<long long> (100 * 100 + 1, - 1));
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        if (i == 0) {
            dp[i][a] = 1;
            dp[i][b] = 1;
            continue;
        }
        for (int j = 0; j <= 100 * 100; ++j) {
            if (dp[i - 1][j] == -1) continue;
            dp[i][j + a] = dp[i][j + b] = 1; 
        }
    }

    if (dp[N - 1][X] == 1) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

풀이

• 스택으로 {번호, 갯수} 를 관리
• top 과 같은 번호 들어오면 지울지 말지 결정
• 다른 번호들어오면 push

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N;
    cin >> N;

    stack<pair<int, int> > st;
    int answer = 0;
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;

        if (st.size()) {
            if (st.top().first == num) {
                if (st.top().second == num - 1) {
                    st.pop();
                    answer -= num - 1;
                } else {
                    int tmp = st.top().second;
                    st.pop();
                    st.push({num, tmp + 1});
                    ++answer;
                }
            } else {
                st.push({num, 1});
                ++answer;
            }
        } else {
            st.push({num, 1});
            ++answer;
        }
        cout << answer << '\n';
    }
}

풀이

• dfs 하면서 리프 노드(간선이 부모랑밖에 없는 노드) 의 L = R = seq++
• 리프 노드가 아니면 자식노드들의 구간 모두 포함하게 구성

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int N;
    cin >> N;
    vector<vector<int> > adj(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<int> L(N + 1, 0), R(N + 1, 0);
    int seq = 1;
    function<void(int, int)> f = [&](int cur, int p) {
        if (adj[cur].size() == 1 && adj[cur][0] == p) {
            L[cur] = R[cur] = seq++;
            return;
        }
        int l = 1e9;
        int r = -1e9;
        for (auto e: adj[cur]) {
            if (e == p) continue;
            if (!L[e] && !R[e]) {
                f(e, cur);
            }
            l = min(l, L[e]);
            r = max(r, R[e]);
        }
        L[cur] = l;
        R[cur] = r;
    };

    f(1, 0);
    for (int i = 1; i <= N; ++i) {
        cout << L[i] << ' ' << R[i] << '\n';
    }
}

풀이

• 각 원소 반복의 끝, 또는 그 부분의 B 값이 양수이면 B 값이 음수 직전까지 의 A 값이 최대이다

코드

• 시간복잡도: $O(N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int TC; cin >> TC;
    while (TC--) {
        long long N, M;
        cin >> N >> M;
        vector<pair<long long, long long> > C(N);
        vector<long long> A(N, -1e9), B(N, -1e9);
        for (int i = 0; i < N; ++i) {
            long long x, y;
            cin >> x >> y;
            C[i] = {x, y};
            B[i] = x * y;
            if (i) B[i] += B[i - 1];
            A[i] = x * y * (y + 1) / 2;
            if (i) A[i] += A[i - 1] + B[i - 1] * y;
        }

        long long answer = C[0].first;
        for (int i = 0; i < N; ++i) {
            if (i < N - 1 && C[i + 1].first < 0 && B[i] > 0) {
                long long k = B[i] / abs(C[i + 1].first);
                k = min(k, C[i + 1].second);
                answer = max(answer, A[i] + k * B[i] + k * (k + 1) * C[i + 1].first / 2);
            } else {
                answer = max(answer, A[i]);
            }
        }
        cout << answer << '\n';
    }
}