4/11
BOJ 24136 - 冊子の配布 (Distribution)
Platinum 4
#greedy #dfs
dfs를 $M$번 돌리며, 돌 때마다 가장 이득이 되는 리프 노드를 찾으면 된다.
Silver 1
#dfs
루트에서 모든 리프까지의 거리 합을 구하면 된다.
Gold 5
#greedy #sorting
인접한 두 원소의 차 중 큰 값을 $N-K$개 더하면 된다.
Gold 3
#case_work
주어진 판에서 나올 수 있는 서로 다른 경우의 수는 6가지밖에 없다.
Gold 5
#sweeping #priority_queue
우선순위를 절댓값이 작은 순으로 설정하고 시작점과 끝점을 PQ에 넣어준 뒤 스위핑으로 해결하면 된다.
Gold 3
#floyd_warshall #bruteforcing
정점의 중복 방문이 가능하기 때문에 플로이드-워셜로 모든 점들 간의 최단 경로를 구해놓고, next_permutation으로 가능한 모든 순열에 대해 최솟값을 구하면 된다.
Gold 1
#constructive #priority_queue
차수가 가장 높은 점부터 뽑아서 다른 점들과 이어주면 된다. 이 때 다른 점들 중 차수가 높은 순서대로 골라야 한다.
4/12
Bronze 1
Platinum 4
#lucas'_theorem #combinatorics
문제를 관찰하면, 요구하는 값은 곧 $\sum \limits_{i=0}^{N-1} {_{N+M-2-i}C_{N-1-i}} + \sum \limits_{i=0}^{M-1} {_{N+M-2-i}C_{M-1-i}}$의 parity임을 알 수 있다.
lucas' theorem으로 각 조합을 계산해주면 된다.
parity만 필요한 거라서, 더 쉬운 다른 방법이 존재할 수도 있다.
Platinum 5
#bitmask #knapsack #primality_test
$1$부터 $50$까지의 소수 개수가 15개임을 이용해, $O(2^{15}N^2)$ knapsack을 돌리면 된다.
BOJ 24618 - Robot Instructions
Platinum 4
#mitm
반으로 갈라서 좌표값 합으로 가능한 모든 경우를 각각 저장하고, mitm하면 된다.
set을 써도 통과하는 것 같은데, 본인은 upper_bound - lower_bound로 구했다.
Gold 5
#stack
스택으로 (통나무의 길이, 개수)를 저장해놓고, 마법 쿼리가 들어올 때 직접 모든 통나무들에 대해 작업을 수행하면 된다.
Gold 4
#pick's_theorem
픽의 정리를 사용하면 된다.
Gold 3
#bfs
모든 가능한 상태는 $2\,985\,984$가지이다. 그냥 bfs를 돌리면 된다.
4/14
Gold 5
#divide_and_conquer #recursion
각 레벨 별 패티의 수와 레이어 수는 점화식을 세워 쉽게 구할 수 있다.
레벨 $N$에서의 패티의 수는 레벨 $N-1$에서의 경우 두 개의 합으로 쪼갤 수 있으므로, 재귀로 풀 수 있다.
4/16
Gold 2
#sorting #priority_queue
현재 위치에서 최대한으로 갈 수 있는 좌표를 $len$이라고 하면, 주유소를 들렀을 때 $len$값이 가장 커지는 곳부터 가면 된다.
즉, 현재 갈 수 있는 곳 중 연료를 가장 많이 주는 곳부터 가면 된다.
Platinum 2
Gold 2
#dp
층간 이동 비용은 같은 층 내의 끝에서 끝으로 이동하는 비용보다 크다. 따라서, 아래로 내려가는 경로가 포함된 최적해는 절대 있을 수 없다. 한 층에 방문해야 하는 모든 칸을 다 방문하고 올라가는 것이 더 이득이다.
이제 각 층의 왼쪽 끝, 오른쪽 끝에 대해 dp를 돌려주면 된다.
4/17
Silver 1
#bruteforcing
만들 수 있는 모든 수에 대해 확인하면 된다.
Bronze 5
OCaml로 입출력, 조건문을 이용해 구현해봤다.
Gold 4
#combinatorics #greedy
초기 상태에서 $1$번 점과 나머지 모든 점들을 한 번씩 이어, $N-1$개의 간선을 만들어주는 것이 최적이다.
그 후로는, 남은 간선 $_{N-1}C_{2}$개를 모두 이어줘야 한다.
Bronze 4
OCaml 연습
Bronze 4
OCaml 연습
Gold 5
#ad_hoc
OCaml 연습
하려했는데, 25%에서 원인 불명의 런타임 에러가 자꾸 발생해서 포기하고 C++로 짰다.
4/18
Gold 2
#sweeping
$N^2$개의 y좌표 중점에 대해 스위핑해주면 된다.
왜 되는지는 잘 모르겠는데, 될 것 같아서 제출하니 AC를 받았다. 더 고민해봐야 할 듯
Silver 1
#prefix_sum #bruteforcing
행, 열에 대한 누적 합 전처리 후 $O(N^2M^2)$ 완전 탐색으로 최댓값을 구하면 된다.
Gold 2
#set #bfs
퍼즐의 상태는 총 $9! ( = 362880)$가지가 존재한다.
한 가지 상태에서 최대 네 가지의 상태로 전이될 수 있다.
$\rightarrow$ bfs로 풀자.
상태의 중복 체크를 할 때 본인은 set을 썼지만, 없어도 적당한 처리를 거치면 정수 하나로 가능할 것 같다.
Platinum 4
#dijkstra #priority_queue
다익스트라를 살짝 변형해서, 각 정점 당 가장 작은 k개의 경로를 max heap에 들고다니면 된다.
Platinum 5
#dp
$N \times M$ 크기의 dp table에서 $dp[n][k]$를 $N$번 도시까지 $M$원을 소비했을 때의 최단 거리라고 생각하면,
1번 점에서 시작해서 이 dp table을 채워주면 된다.
4/19
Platinum 4
#set #map #simulation
A, D 방향과 B, C방향을 묶어서 직선으로 관리하면 된다.
만약 두 점이 A, D방향으로 서로 갈 수 있다면 두 점의 ($y$좌표 - $x$좌표) 값이 같고,
두 점이 B, C방향으로 서로 갈 수 있다면 두 점의 ($y$좌표 + $x$좌표) 값이 같음을 이용하여,
직선을 map<int, set<int>> 형태로 관리하며 각 이동마다 find, erase를 사용하여 시뮬레이션을 할 수 있다.
4/20
Platinum 5
#binary_search #prefix_sum #implementation
구현이 조금 까다로울 뿐이고, 발상 자체는 어렵지 않다.
문자열 $S$의 각 부분이 실제로 $P$에서 어느 위치부터 시작하는 지를 가지고 있으면, 쿼리에서 주어지는 $s, e$를 $S$의 범위로 치환시킬 수 있다.
각 문자 별로 등장한 횟수를 누적 합으로 구하면, 2번 쿼리도 풀 수 있다.
Platinum 2
#bitmask_dp
$A_1$부터 $A_N$까지 $B$의 원소 중 아직 사용하지 않은 수를 하나씩 더해가며 최종적으로 가능한 지 구하면 된다.
재귀함수를 다음과 같이 작성하였다. $sol(n, k, need)$
$n$ : 현재 처리 중인 $A$에서의 인덱스를 의미한다.
$k$ : 현재까지 사용한 $B_i$들의 집합을 정수로 나타낸 것이다.
$need$ : 지금 채워야 하는 수를 의미한다.
$sol(0,0,A_0)$을 돌려주면 되도록 함수를 작성했다. 시간복잡도는 대략 $O(M2^M)$인 것으로 보인다.
'문제 풀이' 카테고리의 다른 글
| BOJ 15683 - 감시 [C++] (1) | 2024.05.01 |
|---|---|
| 4월의 문제 풀이 - (3) (0) | 2024.05.01 |
| 4월의 문제 풀이 - (1) (2) | 2024.04.13 |
| BOJ 1176 - 섞기 [C++] (0) | 2023.12.14 |
| BOJ 24502 - blobsad [C++] (0) | 2023.12.12 |