너무 오래 쉰 것 같다.
종강을 하고도 PS는 종종 했지만, 글 쓰는게 귀찮아서 방치하다가 4개월치나 밀려버렸다.
한 번에 쓰기에는 문제 수가 너무 많아서 4월부터 다시 시작하려 한다...
4/2
Gold 1
#knapsack #dp
모든 사람들의 몸무게 합은 $45\,000$ 이하이고, 사람의 수가 $100$명 이하이다.
따라서, 사람이 한 명씩 추가될 때마다 (몸무게 합, 사람 수)로 가능한 경우를 knapsack dp로 갱신해주면 된다.
Gold 4
#bfs
주어진 $M$개의 파티 정보로 양방향 그래프를 만들고, 진실을 아는 사람들을 시작점으로 한 뒤 bfs를 돌려주자.
bfs 수행 중에 만나는 모든 사람들에게는 거짓말을 할 수 없다.
BOJ 31724 - Hyper Tree Problem
Platinum 4
#bitmask #disjoint_set #tree
문제를 살짝 변형해서, 가중치 값이 $0$ 또는 $1$인 경우에 대해서만 생각해보자.
2번 쿼리에서 $n$과 어떤 점 $i$에 대해 $dist(n,i)$는 트리 상에서 $n$ ~ $i$ 경로에 가중치 $1$인 간선이 존재하면 $1$, 아니면 $0$이다.
$n$을 트리의 루트로 보면, $n$에서 탐색을 시작하며 가중치 $1$인 간선을 만나는 순간, 해당 정점에서의 서브트리에 속하는 모든 점들과의 $dist$는 $1$이 된다.
따라서, $n$과의 $dist$가 $0$인 점들의 개수만 알면 $\sum \limits_{i=1}^{N} dist(n,i)$ 또한 알 수 있다.
분리 집합을 이용해 가중치 $0$인 간선에 대해 두 정점을 한 집합으로 합쳐주며 관리하면 된다.
또, bitwise연산은 정수를 이진수로 나타내었을 때 각 비트에 대해 독립적이기 때문에 모든 비트들에 대해 트리를 만들어주면 된다.
Platinum 5
#dijkstra
주어지는 방향 간선 $(u,v,d)$에 대해 반대 방향 간선 $(v,u,2d)$를 추가해주고 다익스트라를 수행하면 된다.
다른 모든 건물에 대한 최단 도달 시간의 합을 최소화한다는 말은 곧 모든 건물로의 최단 시간을 최소화시켜야 한다는 것이므로 그냥 다익스트라를 돌려주면 된다.
반대 방향 간선을 타는 일이 생기면 해당 간선에 대한 답을 $0$으로 바꿔주기만 하면 된다.
어떤 간선 $(u, v)$를 타는 최단 경로가 있으면 $(v, u)$를 타는 최단 경로는 없기 때문이다.
4/4
Gold 5
#disjoint_set
분리 집합을 굳이 안 써도 되지만, 쓰면 구현이 편해진다.
Gold 5
#bfs
구간을 정점으로 보고, 구간끼리의 이동 가능 여부를 간선으로 보는 그래프를 관리하면 된다.
2번 쿼리는 bfs로 처리하자. 제한이 작아서 충분히 시간 내에 들어온다.
Platinum 4
#bitmask_dp #game #math
$K$개의 카드를 모두 사용하는 경우를 $1$회 순환했다고 말할 수 있다.
$B-A \ge \dfrac{K(K+1)}{2}$인 경우에는 $s$회 순환하면 항상 $B-A < \dfrac{K(K+1)}{2}$인 경우로 만들어줄 수 있다.
$K$와 $s$가 모두 홀수이면 선공이 바뀜에 유의해야 한다.
이제 게임에는 $K \times 2^{K}$ 가지 경우만 존재할 수 있고, bitmask dp로 처리해주면 된다.
$Q$번의 쿼리마다 직접 수행하면 시간 초과이므로 미리 모든 경우를 전처리해주면 된다.
Platinum 5
#disjoint_set #sorting
높이가 가장 낮은 땅부터 보면서, 인접한 칸들 중 더 작은 칸들이 있다면 분리 집합으로 합쳐주면 된다.
비슷한 난이도를 가진 유사한 문제가 많이 있다.
Platinum 3
#priority_queue
행, 열을 따로 압축해주면 된다.
각각의 압축은 (원소, 인덱스)를 관리하는 우선순위 큐로 진행하면 된다.
Platinum 1
#segtree
연속합과 쿼리의 응용 버전이다.
원하는 결과를 얻을 수 있도록, 세그트리의 각 노드에 필요한 값을 모두 가지고 있으면서 잘 합쳐주면 된다.
Bronze 2
#math
$n$개의 $1$, $n-1$개의 $0$을 출력하면 된다.
Gold 3
#knapsack #dp
knapsack dp로 $dp[i]$를 구해주고, 각 $K_i$마다 $\dfrac{\max(dp[1], \cdots, dp[K_i])}{K_i}$를 구해주면 된다.
Platinum 4
#lucas'_theorem #combinatorics
뤼카 정리의 기본 문제이다.
쿼리 형식의 문제였으면 DP로 $O(M^2)$에 combination 값을 전처리해야 하지만, 그게 아니기 때문에 매번 직접 계산해줘도 된다.
4/8
Gold 4
#knapsack #dp
$O(NK)$ knapsack으로 해결할 수 있다.
Bronze 3
#implementation
'X'만 존재하는 열 중 가장 번호가 작은 걸 출력하면 된다.
Silver 1
#math #binary_search
$X$가 몇 번째 대각선에 속해있는지를 이분 탐색으로 찾고, parity에 따라 맞는 값을 출력해주면 된다.
Gold 2
#math
$F(n)$을 $0$부터 $n$까지 $0$이 등장하는 횟수라 정의하고, 각 자릿수별로 $0$이 몇 번 등장하는지를 모두 합쳐주면 $F(n)$을 구할 수 있다.
$F(m) - F(n-1)$을 구하면 된다.
4/9
BOJ 15777 - Xtreme NP-hard Problem?!
Diamond 4
#mitm #case_work #graph
$n$ 혹은 $m$이 $5$ 이하인 경우에는 가능한 경로를 어떻게든 모두 구하면 된다. (본인은 재귀 람다식으로 구현했다.)
$k$가 $5$ 이하인 경우는 if문 다섯 개로 나눠서 각각 따로 처리해주었다.
$k = 1$일 때는 $(1, n)$간선, $k=2$일 때는 $(1,p)$와 $(p,n)$간선에 대해 확인해주었다.
$k \ge 3$일 때는 $1$, $n$ 각각에서 뻗는 길이 $2$이하인 경로들을 적절히 합쳐주며 구했다.
경로 두 개를 합칠 때, 중복되는 정점이 없도록 최솟값의 후보들을 여러 개 관리해야 해서 구현이 힘들었다.
Gold 3
#dp #sorting
최솟값부터 보면서 dp테이블을 구성해주었다.
어떤 점 $(x,y)$에서의 $dp[x][y]$는 인접한 네 방향의 max dp값 + 1이 된다.
4/10
Gold 5
#greedy
counting 배열을 만들고, $1$부터 $N$까지 보면서 $cnt[i] > 1$인 $i$에 대해 $cnt[i] = 1$이 될 때까지 $pK + i$꼴로 바꿔주면 된다.
이렇게 했을 때 $1$ ~ $N$이 모두 만들어지지 않으면 불가능하다.
Platinum 5
#implementation #parsing #recursion
그냥 문제에서 주어진 BNF를 통째로 재귀로 구현하면 된다.
본인은 평소에 코드를 작성하는 속도가 느리지 않다고 생각하는데도, 생각 20분에 구현이 40분이나 걸렸다.
.
.
.
앞으로 열심히 쓰겠습니다..
'문제 풀이' 카테고리의 다른 글
| 4월의 문제 풀이 - (3) (0) | 2024.05.01 |
|---|---|
| 4월의 문제 풀이 - (2) (0) | 2024.04.22 |
| BOJ 1176 - 섞기 [C++] (0) | 2023.12.14 |
| BOJ 24502 - blobsad [C++] (0) | 2023.12.12 |
| BOJ 9015 - 정사각형 [C++] (0) | 2023.12.12 |