10/11 ~ 10/20에 푼 문제들입니다.
문제의 풀이에 대한 스포일러가 포함되어 있습니다.
잘못된 풀이가 있다면 지적해주세요.
10/11
Gold 4
#math #tree
$p<q$인 경우는 답이 $q/q-p$이다. $p>q$인 경우는 $p<q$가 될 때까지 트리에서 부모를 타고 올라간 후 $q/q-p$로 넘어간 뒤 올라온 횟수만큼 다시 왼쪽 자식을 타고 내려가면 된다.
Platinum 5
#dp_tree #dfs #recursion
정점 $n$의 왼쪽 자식과 오른쪽 자식을 각각 $l, r$이라고 하자. $n$을 루트로 갖는 dfs를 실행할 경우 $n$의 서브트리의 정점 수만큼의 탐색이 진행된다. 이 때, $l$을 루트로 하는 dfs는 두 번 수행되므로 서브트리의 수 $sub[n] = 2sub[l] + sub[r] + 1$로 정의하자. 이는 한 번의 dfs로 쉽게 구할 수 있다. 이제 루트에서부터 내려가며 $K$가 각 서브트리 내에서의 탐색 범위에 들어오는 지 확인하자.
Unrated
$a$와 $b$가 같다면 최대 $a-1$번 역전이 일어날 수 있다. (0:0인 경우는 예외) 그렇지 않은 경우엔 항상 둘 중 최솟값만큼 역전이 가능하다.
Gold 5
#combinatorics
각 점에 대해, 해당 점이 직각삼각형의 직각을 이루는 점일 때의 가능한 직각삼각형의 수를 세주면 된다. 해당 점의 좌표를 $(x,y)$라고 하고 $cols[i]$와 $rows[i]$를 각각 $i$번째 열, 행에 존재하는 점의 수라고 하면, 그 개수는 다음과 같다. $(cols[x]-1) \times (rows[y]-1)$
10/12
Silver 1
#dp
$dp[i][j]$를 길이가 $i$이면서 $j$로 시작하는 줄어들지 않는 수라고 정의하고 문제를 해결하자.
Gold 5
#greedy #sorting #two_pointers
내림차순 정렬한 뒤 $s=1, e=N$으로 잡고 $s$쪽으로 바구니가 터질때까지 나도리를 넘겨주면 된다.
Gold 1
#prime_factorization #sieve_of_eratosthenes
2부터 $n$까지 소인수분해를 진행했을 때 각 소수가 나온 횟수를 $cnt[p]$라고 하자. 0보다 크면서 짝수인 $cnt[p]$들에 대해 $p^{cnt[p]}$를 모두 곱해주면 그 수는 완전제곱수가 된다. $sieve[n]$에 $n$을 나누는 가장 작은 소인수를 저장하면 소인수분해를 빠르게 할 수 있다. 2부터 10,000,000까지 모든 수를 소인수분해해서 $n$이하일 때의 답을 미리 전처리하자. 놀랍게도 시간 안에 돈다. 정답을 저장하는 배열을 long long으로 선언했다가 MLE를 맞고 #offline_query로 풀었는데 생각해보니 답은 항상 int범위안에 든다. int로 선언해주면 AC를 받을 수 있다.
10/13
Platinum 5
#bruteforcing #math
개수 제한을 보자마자 next_permutation이 떠오르는 문제이다. 넥퍼뮤로 가능한 모든 순서에 대해 최솟값을 구해주자. 이 때 어떤 원의 지름이 다른 원의 지름을 포함하는 경우를 조심해서 구현하자.
Gold 1
#binary_search
주어지는 수들의 범위가 백만까지이다. 각 숫자가 나온 인덱스를 오름차순으로 저장하면, 쿼리는 자연스레 이분 탐색으로 해결할 수 있다. 쿼리의 수열 길이 합이 백만이기 때문에 $O(N\log_{N})$에 해결할 수 있다.
Gold 5
#bruteforcing
가능한 경우의 수는 $2^6$개이다. 완전 탐색을 돌리자.
Gold 4
#math
높이가 $i$인 직사각형의 개수는 $\dfrac{n}{i} - (i-1)$개이다. 이 때, 높이가 $\sqrt{n}$을 넘어가면 대칭성에 의해 중복계산이 되므로 $i \le \sqrt{n}$까지만 계산하자.
Gold 5
#prefix_sum #math
구하려는 값을 $F_{k}$라고 하자. $F_{1} = a_{1}$이고, $F_{2} = F_{1} + 3a_{1} + a_{2}$, ... 와 같이 쓸 수 있다. $F_{k} = F_{k-1} + D_{k}$와 같이 쓰면 누적 합 두 개로 해결할 수 있을거 같은데.. 라는 생각이 중요하다. $F_{1} = a_{1} = D_{1}$이라 하면, $D_{2} = 3a_{1} + a_{2} = D_{1} + 2a_{1} + a_{2}$이다. $D_{3} = D_{2} + 2a_{1} + 2a_{2} + a_{3}$, ... . 느낌이 오는가? $D_{k} = D_{k-1} + \sum\limits_{i=1}^{k-1}a_{i} + a_{k}$이다. $F$와 $D$, $SUM$을 잘 유지하며 구현하자.
Gold 5
#sorting #two_pointers
우선 $x$가 cm단위이기 때문에 nm으로 바꿔준다. 정렬하고 양끝에서부터 좁혀나가며 합이 $x$가 되면 출력해준다.
10/14
Gold 2
#bfs #precomputation
모든 p에 대해 답을 깡bfs로 구해놓고 DB를 끌고와서 제출하자. 돌려보면 알겠지만, 어떤 p에 대해서도 답이 20을 넘지 않는다.
Platinum 3
#sorting #dp #greedy
$a_i$와 $b_i$가 쌍을 이룰 필요없이 최적의 순서를 찾아가는 문제이다. 먼저 오름차순 정렬을 해놓자. $a_i = b_i$인 쌍이 있다면, 이것을 순서를 적절히 바꿔서 없애줘야 한다. $a_i$와 $a_j$를 바꾼다고 하자. 이 때, $|i-j| > 1$인 $j$는 최적해를 만들어줄 수 없다는 관찰이 필요하다. 즉, 앞뒤로 한 칸만 검사해주면 된다. $dp[i]$를 $i$번째 트럭까지 처리했을 때의 가능한 최솟값이라 하고 $addv[i][j]$를 구간 $[i-j+1, i]$에서 모든 가능한 배치 중 최솟값이라 할 때 , $dp[i] = min(dp[i-1] + addv[i][1], dp[i-2] + addv[i][2], dp[i-3] + addv[i][3])$이다.
Platinum 1
#miller_rabin_primality_test
대학교 과제에서 밀러-라빈 소수판별법을 구현하는 게 나왔는데, 이번 기회에 배워서 풀어봤다. 위키피디아를 참고해서 검사 값으로 $a = 2, 7, 61$인 경우만 확인했다.
10/15
Gold 1
#mst
주어진 거리 중 제일 짧은 것은 반드시 간선이 된다는 관찰이 필요하다.
BOJ 25938 - Towers of Hanoi Grid
Gold 5
#math
가장 큰 원판이 제일 먼저 도착점에 갈 수 있어야 한다. 그럴 수 있으면, 나머지 원판들도 항상 도착점에 갈 수 있다.
Gold 5
#string #sliding_window
substr로 길이 $K$인 것을 모두 검사해 정답 문자열에 넣거나 뺀다.
Gold 1
#sorting #disjoint_set
분리 집합으로 각 스터디 별 $i$번 직원의 root를 구해서, 임의의 튜플 $T[i]$에 각각 넣어준다. 튜플의 값이 같은 것들끼리는 굉장한 모비스터디이다.
(shake! 2022에 나왔던 문제인데, 대회에 참가했을 당시에는 풀지 못했던 문제다. 랜덤 돌리다가 익숙한 지문이 나와서 풀어봤는데 그 땐 왜 못 풀었는지 이해가 안 된다. 그 때보다 실력이 오른 것 같아서 좋다.)
Silver 3
#math #number_theory
$H = 3$까지만 직접 해봐도 모듈로의 성질만 알면 금방 풀 수 있다.
Gold 4
#case_work
if else로 코드를 꽉 채우면 풀 수 있다.
BOJ 24143 - カンニング対策 (Cheating)
Gold 3
#sorting #parametric_search #binary_search
$x, y$를 따로 생각해도 된다. 각 좌표를 입력받아 정렬 후, $d_{max}$에 대해 parametric search로 최솟값을 찾자. $1$부터 돌렸다가 한 번 틀리고나서 생각해보니 감시 범위가 $0$일 수도 있다는 걸 깨달았다.
Gold 1
#dfs #dp_tree
$dp[i][0], dp[i][1]$을 각각 $i$번 직원이 불참/참석했을 때의 $i$를 루트로 하는 서브트리 최댓값으로 정의하자. $dp[i][0] = \sum{max(0, dp[child][0], dp[child][1])}$이고, $dp[i][1] = \sum{max(0, dp[child][0])}$이다. 추적은 따로 함수를 만들어서 해줬다.
10/16
Gold 1
Gold 2
#dfs #dp_tree
이것도 거의 같은 문제인데, 약간의 관찰이 더 필요하다. 이게 왜 티어가 더 낮은지 잘 모르겠다.
Gold 2
#dfs #dp_tree #sorting
각 정점 $i$마다, $i$를 루트로 갖는 서브트리에서 뉴스를 전하는 데 걸리는 최소 시간을 $dp[i]$로 정의하면 쉽게 풀 수 있다. $i$의 자식의 집합을 $child$라 하자. 어떻게 하면 $dp[i]$가 최솟값을 가질까? $i$번 정점에서 $child$의 모든 정점에게 한 번씩 뉴스를 전하므로 각각의 자식은 $1, 2, \cdots, child.size()$만큼의 시간 후에 뉴스를 받게 된다. 가장 오래 걸리는 자식부터 차례대로 전해주면 된다.
Platinum 5
#prime_factorization
주어진 식의 좌변에 $y$만 남기고 정리하면 $y = \frac{nx}{x-n}$이 된다. 여기서 조건 $x > n$이 생긴다. $x$는 $n$보다 큰 정수여야 하므로 임의의 정수 $t (t > 0)$에 대해 $x=n+t$로 표현해보자. 그러면 $y = \frac{n(n+t)}{t} = \frac{n^2}{t} + n$가 되고, $y$또한 정수여야 하므로 $t$가 $n^{2}$의 약수여야 한다. $x = n+t, y = n+\frac{n^2}{t}$이므로 $t > n$이면 $x <= y$의 조건에 위배된다. 최종적으로, $n^2$의 약수 중 $n$이하의 개수를 세주면 된다.
Gold 1
#disjoint_set #dfs #constructive #case_work
주어진 간선들로 스패닝 트리를 만들자. 만약 주어진 그래프가 연결 그래프라면 1, N-1사이즈로 분할하면 된다. 연결 그래프가 아닌 경우에는, 컴포넌트 수가 3개 이상이면 절대 두 개의 트리로 분할할 수 없다. 컴포넌트 수가 두 개라면 dfs 2번으로 각각의 트리를 구해주되, 트리의 사이즈가 같은 경우를 예외처리 해줘야 한다. (이걸 안해주면 97%에서 틀리는 고통을 맛보게 될 것)
Gold 4
#stack
스택에 {value, index}를 저장해놓고, top의 value보다 작은 값이 들어오면 해당 인덱스의 답은 (현재 인덱스) - (top의 index)이다. 해당 값으로 초기화된 적이 없다면 infinity를 출력하자. 오큰수와 똑같은 문제다.
Gold 2
#dp #topological_sorting
최초에 1을 넣고 위상 정렬을 수행하며 dp테이블을 채워주면 된다. 경로 추적은 N의 제한이 작아 각 정점별 최대 경로를 직접 저장하는 식으로 해도 된다.
Gold 2
#bruteforcing #map #geometry
정팔면체의 동형 32가지의 방문 여부를 모두 map에 넣고 가능한 모든 조합을 next_permutation으로 counting해주자.
Gold 1
#math
$n = n-m$으로 놓고, $m - ( (m \& 1 \oplus 1) + 1 )$ 값을 비트로 나타낸 수열을 $b_i$라고 하자. $b_i$를 왼쪽부터 읽었을 때 처음 나오는 $1$ 혹은 $0$바로 뒤에 나오는 $1$들의 index를 $one$라 하고, $1$바로 뒤에 나오는 $0$들의 index를 $zero$라 하자. 가능한 모든 $one, zero$에 대해 $n\bmod 2^{one} < 2^{zero}$를 만족하면 답은 1, 아니면 0이다. m=32까지 직접 찍어보면서 규칙을 찾았다.
Diamond 5
#miller_rabin_primality_test
$K = 5$라고 하자. $K$에 3 이상의 임의의 소수 $p$를 곱했을 때, $K$이상 $pK$미만의 수 중 $p$가 등장하는 횟수는 반드시 2번 이상이다. 따라서 $pK$는 key가 될 수 없다. 즉, 소수인 $K$만 출력해주면 된다. 위의 조건에서 소수가 아닌 홀수 중 key인 수는 9밖에 없다. if문으로 예외처리 해주자.
Gold 3
#flow
network flow에 대해 배웠다. 이해하는 데 상당히 오래 걸렸다. 구현은 에드몬드-카프 알고리즘으로 했다.
Platinum 4
#flow
간선의 수가 많을 때 사용하기 좋은 디닉 알고리즘을 배웠다. 가장 기본적인 문제인 듯 하다.
Gold 3
#greedy
$O(N^2)$ 코드가 AC를 맞았다. 나중에 다시 풀어봐야겠다.
Gold 2
#sorting #combinatorics
정렬된 수열을 $a_{1}, a_{2}, \cdots, a_{N}$이라고 하자. 최솟값이 $ai$이고 최댓값이 $aj$인 구간을 고르는 경우의 수는 $2^{j-i}-1$이고, 이 때 $a_{i+1}, a_{i+2}, \cdots, a_{j}$가 더해지는 횟수는 각각 $1, 2, \cdots, 2^{j-i-1}$회이다. 이 관찰로 전체 $i, j$의 경우를 고려하면 $a_i$가 더해지는 횟수는 총 $2^i - 2^{n-i-1}$이다.
10/17
Diamond 5
#disjoint_set #hld #lazyseg #offline_query
주어지는 쿼리를 일단 전부 다 받아서 1번 쿼리에 대해서만 미리 그래프를 만들어놓자. 이미 경로가 존재하는 두 정점 사이에는 간선이 생기지 않으므로 그래프는 모두 트리가 된다. 둘 사이에 경로가 존재하는지 여부는 분리 집합을 이용하면 된다. 쿼리의 요구 사항이 특정 경로에 대한 구간 합을 요구하므로 heavy-light decomposition을 수행해준다. 이 때, 트리가 여러 개일 수도 있어서 모든 트리에 대해 수행해야 함을 잊지 말자. 간선에 가중치를 달아주고 비포장도로는 1, 포장도로는 0으로 관리해주자. 도로가 포장될 때 구간 업데이트가 필요하므로 lazy를 곁들여 구현해야 한다.
Gold 2
#prefix_sum
$o_{i} - d_{i}$의 누적 합 배열에서 가장 작은 원소를 $a$라고 하자. 답은 $N-(a$의 등장 횟수$)$이다.
10/18
Gold 2
#prime_factorization #sieve
$bad_{i}$를 수 $i$의 나쁨이라고 하자. $n$의 모든 약수의 합을 $f$라고 한다면, $bad_{i} = \lvert f - 2i \rvert$ 이다. $f$는 어떻게 해야 구할 수 있을까? $n$을 소인수분해한 결과가 $ = {p_{1}}^{q_{1}}\times{p_{2}}^{q_{2}}\times\dots\times{p_{m}}^{q_{m}} (p_{i}$는 소수$)$ 일 때, $f = \prod\limits_{i=1}^{m} \dfrac{{p_{i}}^{q_{i}+1}-1}{p_{i}-1}$이다.
10/19
BOJ 15789 - CTP 왕국은 한솔 왕국을 이길 수 있을까?
Gold 4
#graph_traversal #greedy #sorting
각 동맹의 크기을 구한 뒤, $C$와 $H$를 제외한 동맹 크기 중 큰 것 $K$개를 가져오자.
Gold 5
#combinatorics
입력 제한을 제외하면 이 문제와 똑같은 문제다. 0-based index인 수열 $A$의 모든 부분집합에서 최댓값이 $A_i$가 되는 경우는 $2^i$가지이고, 최솟값이 $A_i$가 되는 경우는 $2^{N-i-1}$가지이다. 따라서 답은 $\sum \limits_{i=0}^{N-1} (A_{i}\times(2^i - 2^{N-i-1}))$이다.
Gold 3
#math
$N\times M$ 미만의 어떤 수 $g$에 대해, $\sqrt{g}$이하인 $g$의 어떤 약수 $i$가 $\lvert \dfrac{g}{i}-i-D_{old} \rvert \le K$를 만족하는지 확인하자.
Gold 2
#dfs
dfs를 수행하면서 만약 사이클이 생겼다면 지나왔던 모든 점들은 정답 후보에서 제외된다.
Gold 2
#sieve_of_eratosthenes #prefix_sum
$upper[N]$을 $N$이상의 가장 작은 소수, $lower[N]$을 $N$이하의 가장 큰 소수라고 하고, $idx[N]$은 $N$이 몇 번째 소수인지를 나타내도록 $1 \le N \le 100,000$ 범위 내에서 미리 구현해놓자. 그러면 각 쿼리 $F(a,b)$는 $F(upper[a], lower[b])$와 같다.
$upper[a]$가 홀수 번째인 경우와 짝수 번째인 경우 두 가지로 나눠서 생각해보면, 누적 합 배열 두 개로 모든 쿼리를 처리할 수 있음이 보인다.
$F1[i]$을 $2$부터 $i$번째 소수까지의 주어진 수식 값이라 하고, $F2[i]$를 $3$부터 $i$번째 소수까지의 수식 값이라고 하면, $F(a, b)$는 $F1[idx[lower[b]]] - F1[idx[upper[a]]-1]$ 혹은 $F2[idx[lower[b]]] - F2[idx[upper[a]]-1]$이다.
BOJ 23432 - Steve's perfectionism
Gold 5
#constructive
첫 번째 수는 그대로 넣고, $i$번째 수는 $i-1$번째 수보다 크면서 가장 작은 $a_i$의 배수를 넣자.
끝
'문제 풀이' 카테고리의 다른 글
| 11월의 문제 풀이 - (1) (0) | 2023.11.11 |
|---|---|
| 10월의 문제 풀이 - (3) (1) | 2023.11.01 |
| 10월의 문제 풀이 - (1) (1) | 2023.10.12 |
| 9월의 문제 풀이 - (2) (1) | 2023.10.03 |
| 9월의 문제 풀이 - (1) (0) | 2023.09.27 |