BOJ8 BOJ 14435 링크 내가 지금까지 풀었던 문제 중에 단연코 세 손가락 안에 들 정도로 정말 정말 좋은 문제라고 생각한다. 어떻게 이런 문제가 고등학교 교내 대회에 나왔는지 의문이다. 완전히 내가 푼 것은 아니고 업데이트 횟수를 줄이는 것이 핵심 아이디어라는 힌트를 보고 문제를 해결하였다. 이 문제는 자라는 키를 변화시켜서 온라인 처리를 강제했다. 따라서 나이브한 풀이를 생각해 본 후 최적화를 고민할 것이다. 모든 날짜에 모든 질문을 확인한다면 $O(KQ)$에 문제를 해결할 수 있다. 모든 질문을 확인하는 것이 비효율적이므로 가능한 후보들을 줄이는 방법을 고민해 보자. 두 아이의 키의 합이 $k$이상이려면 어떤 조건이 필요할지 생각해 보자. 둘 중 하나의 키는 $k \over 2$ 이상이어야 한다. 어쩌면 당연하게 보.. 2025. 9. 5. BOJ 11027 링크 5월에 gggkik와 랜덤으로 뽑은 문제를 풀다가 나온 문제이다. 장장 3일 동안 고민했을 만큼 매우 어려운 문제라고 생각한다. 여담으로 gggkik는 잠깐 고민하더니 모르겠다고 도망갔다.. 꽤 좋은 문제라고 생각해서 블로그 글을 작성하려고 했는데, 풀이를 설명할 엄두가 나지 않아서 이제서야 작성한다. 문제는 매우 간단하다. $swap$ 연산으로 선택 정렬을 구현한 의사 코드가 주어지고, $N$개의 수에 대해 $M$번째 원소까지 선택 정렬을 수행했을 때의 $swap$ 연산 횟수를 출력하면 된다. 먼저, 몇 번의 시뮬레이션을 통해 어떤 규칙이나 패턴이 있는지 파악해 보자. 어떤 $i$에 대한 연산이 일어나기 전 처음 수열과 마지막 수열을 비교해 보자. 전체 수열을 $A$, 연산에 참여한 수로만 .. 2025. 9. 4. BOJ 33601 먼저 목표 지점인 포르투에서부터 각 정점까지의 최단 거리 rd를 너비 우선 탐색으로 구해야 한다. 이 거리를 기준으로 하면 모든 최단 경로는 거리 값이 1씩 줄어드는 방향으로만 내려간다. 경찰이 지연 효과를 내기 위해서는 이러한 최단 경로 상의 도로를 끊어야 하므로, 거리 차가 0 또는 1인 두 정점 사이의 도로들만이 차단 후보가 된다. BFS 과정에서 최단 거리 트리를 만들고, 트리 간선이 아닌 후보 도로마다 (rd[u]+rd[v], u, v)라는 3중 튜플을 모은다. 첫 번째 성분인 rd[u]+rd[v]는 u, v에서 각각 부모로 가는 도로가 끊겼을 때 서포터즈가 다른 쪽으로 우회하기 시작하는 시간을 의미한다. 이를 오름차순으로 정렬한 뒤, 거리 트리 위에서 유니온 파인드를 이용해 두 정점을 가장 가.. 2025. 5. 3. BOJ 17533 땅따먹기를 하다 발견한 문제이다. 처음에는 P5로 기여돼 있어서 만만하게 보고 풀기 시작했지만 정말 어려운 문제였다. 그리디한 접근이 가장 직관적으로 떠오르지만 그건 함정이었고, 실제로는 빈 수조가 있을 경우에 답이 완전히 달라지기 때문에 그리디와 배낭 문제를 결합해서 풀어야 한다. 자세한 풀이는 위 슬라이드를 참고하면 된다. 더보기#include using namespace std;using ll = long long;using pll = pair;constexpr ll INF = 1LL > n; vector v; for (ll x, y, i = 0; i > x >> y; m += x; if (!y) { emp++; } else { .. 2025. 5. 3. BOJ 25055 2차원에서 생각해 보면 저 두 그래프의 오른쪽에 있을 경우에만 이동할 수 있다. 기울기가 모두 같기 때문에 기울기가 양수인 그래프의 경우 y절편이 감소해야 하며, 기울기가 음수인 그래프의 경우 y절편이 증가해야 한다. 따라서 기울기가 양수인 경우를 내림차순 정렬한 후, LIS를 구하면 된다. 단, 불가능한 경우를 제외해 줘야 한다. #include using namespace std;using ll = long long;using pll = pair;inline void init() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);}int main() { init(); ll n, v; cin .. 2025. 2. 14. BOJ 16615 a_i >= a_i-1인 경우에는 왼쪽으로 i-1부터 더하는 것이 가능하므로 고민하지 않아도 된다. 하지만 a_i #include using namespace std;using ll = long long;inline void init() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);}int main() { init(); ll n; cin >> n; vector v(n); for (auto& x : v) { cin >> x; } bool ans = true; for (ll cur = 0, i = 1; i v[i]) ans = false; .. 2025. 2. 13. 이전 1 2 다음
