10/21 ~ 10/31에 푼 문제들입니다.
문제의 풀이에 대한 스포일러가 포함되어 있습니다.
잘못된 풀이가 있다면 지적해주세요.
10/21
BOJ 9741 - Interior Lattice Points
Gold 3
#pick's_theorem #polygon_area
픽의 정리란? 2차원 격자 위의 단순 다각형에 대하여, 다각형의 넓이를 $a$, 다각형의 변 위에 존재하는 정수 좌표 점의 수를 $b$, 다각형의 내부(경계 미포함)에 존재하는 정수 좌표 점의 수를 $i$라고 하면 $A = i + \dfrac{b}{2} - 1$가 성립한다. 이 식을 $i$에 대해 정리해서 풀자. 세 점이 일직선상에 있는 경우를 조심하자.
10/22
Gold 4
#dfs
같은 연결 요소 내에서는 방문할 수 있는 { 청정수, 고인물 } 물탱크의 값이 같다. 연결 요소마다 dfs로 값을 구해주자.
Gold 3
#topological_sorting #set
간선 $(a, b)$를 뒤집어서 $(b, a)$를 $b$가 $a$보다 늦게 일어난 사건이라 정의해도 문제를 푸는 데는 지장이 없으므로 전부 뒤집어주자. 이 그래프에서 위상 정렬을 수행하면 사건 $i$보다 늦게 일어난 사건은 항상 $i$보다 먼저 처리 된다. 각 사건마다 set을 할당해 자신보다 늦게 일어난 사건을 모두 저장하도록 하자.
(문제를 풀고 알고리즘 태그를 보니 더 쉬운 풀이가 있는 것 같다.)
BOJ 16110 - Kiwis vs Kangaroos II
Gold 2
#sorting #constructive
많이 등장하는 친구들부터 대각선으로 채워넣으면 된다.
Gold 2
$N$원을 만드는 데 필요한 최소 동전 개수를 $f(N)$이라 하면, $f(N) = f(\lfloor \dfrac{N}{100} \rfloor) + f(N \bmod 100)$이다. $100$이하의 케이스에선 미리 전처리로 답을 구해놨다.
Gold 1
#tree #recursion
현재 $N$번째 피이보나치 트리의 루트에 있고 그 번호가 $root$이면서 $K$번 점을 찾으러 가야한다고 하자. 만약 $K$가 $root$이면 더 이상 탐색할 필요가 없다. 전위 순회로 번호를 매기니까 왼쪽 서브트리에 존재할 수 있는 번호는 $[root+1, root+(N-2$번째 피이보나치 트리의 크기$)]$가 된다. 이 범위에 들어오면 왼쪽으로 내려가고, 아니면 오른쪽으로 내려가자. 이걸 재귀적으로 수행하면 $K$를 찾을 수 있다.
이렇게 $1$번 점에서 시작점, 끝점으로 가는 경로를 각각 구한 뒤, 적절히 합쳐주자.
BOJ 25337 - Merge the Tree and Sequence
Platinum 4
#set #disjoint_set #sorting #greedy
각 구역에 속한 정점들의 $A$의 합을 $S$라 하자. 어떤 정점 $i$가 점수에 관여하는 방식은 $A_i$에 계수 $F_i$가 곱해진 값을 점수에 더하는 것이다. 이 $F_i$의 값은 $i$가 속한 구역의 $S$의 합이다. 구현이 조금 귀찮지만, 모든 구역을 다 구해서 $F_i$값을 구하고, $F_i \times B_i$를 적절히 최대, 최소로 만들어 출력해주면 된다.
Silver 2
#prefix_sum #sliding_window
$S_i$를 $i$번째 횡단보도까지 꺼져있는 신호등의 총 수로 하면, 누적 합으로 $S_i$를 구할 수 있다. $S_i - S_{i-K}$는 $i-K+1$부터 $i$까지 꺼져있는 신호등의 수고, 이것들의 최솟값을 구해주면 된다.
Bronze 1
#implementation
$row[i]$와 $col[i]$를 각각 $i$번 행, 열에 경비원이 있는지의 여부로 정의하자. $row[i] = 0$인 $i$가 있으면 $row[i] = 1$로 만들어주고 추가로 $col[j] = 0$인 아무 곳이나 $1$로 만들어주면 된다. 더 이상 0인 $row[i]$나 $col[i]$가 없을 때까지 반복하자.
Gold 5
#combinatorics
연속된 문자가 나온 경우, 해당 문자 두 개의 앞뒤로 존재하는 문자의 수의 곱이 successful string이다. 하지만 이렇게 계산하면 중복 계산이 있을 수 있다. 중복을 피하려면, 연속된 문자의 뒤에 나오는 문자들에 또 연속된 것이 있으면 안 된다. 따라서, 식으로 정리하면 다음과 같다.
문자열 $S$에서 $S_i = S_{i-1}$인 모든 $i$의 집합을 $A_0, A_1, \cdots, A_k$라 하자. 수열 $B_0 = 0, B_i = A_i, B_{k+2} = \lvert S \rvert$라 하면, 모든 successful string의 수는 $\sum \limits_{i=1}^{k+2} {B_{i-1} \times (B_i - B_{i-1})}$이다.
Platinum 4
#greedy #priority_queue
주어지는 수열을 페이지 참조 순서로 본다면, 페이지 교체 알고리즘을 적용할 수 있다. 가장 이상적인 알고리즘은 OPT이고, 우리는 순서를 미리 알고 있기 때문에 이를 적용할 수 있다. 멀티탭이 꽉 차면, 앞으로 가장 오랫동안 사용되지 않을 전기용품을 빼자. 시간복잡도 최적화를 위해 우선순위 큐가 필요하다.
10/23
Gold 3
#segtree
수 $i$에 대해 조건을 판별할 때, 가장 처음 나온 $i$와 가장 나중에 나온 $i$에서만 고려해주면 된다. 최댓값을 관리하는 세그먼트 트리로 구간에 $i$보다 큰 수가 있는지 판별하자. 바보같이 정렬된 배열도 아닌데 upper_bound를 쓰는 만행을 저질렀다가 틀렸다. 세그먼트 트리가 정해는 아닌 것 같지만 방법을 못 찾았다.
Gold 3
#prime_factorization #bruteforcing
모든 수의 합을 $S$라고 하면, 정답이 될 수 있는 수는 무조건 $S$의 약수 중에 있다. $S$를 소인수분해해서 $S$의 모든 약수를 구해준 뒤, 각각에 대해 구간을 나눌 수 있는지 판별하자.
10/24
Gold 5
#simulation
$O(HW)$로 블럭을 채워준 뒤, $y$축을 기준으로 고이는 빗물을 계산해서 더해주는 방식으로 풀었다.
Gold 5
#prefix_sum
위의 빗물 문제와 제한을 빼면 아예 똑같은 문제다. $i$번째 블럭에 고이는 빗물의 양은 $i$번째 블럭의 좌, 우로 가장 높은 블럭에 의해 결정됨을 이용하자.
BOJ 25647 - Oscar's Round Must Have a Constructive Problem
Gold 2
#constructive #sorting
풀이 방법이 사람마다 다 다를 것 같은 문제다. 조금 복잡한데, $1$부터 $N$까지의 수에 대해 각각 등장 횟수, 등장 인덱스를 구해서 등장 횟수가 가장 많은 순서대로 정렬해줬다. 가장 많이 등장한 수부터 해당 자리에 다른 수들을 넣어 대체해줬는데, 이 때 대체하는 수들은 등장 횟수가 많은 순으로 배치해줬다. 등장 횟수가 가장 많은 수는 예외적으로 가장 뒤에 배치해줬다.
Silver 2
#prime_factorization
$N = {p_{1}}^{q_{1}} \times {p_{2}}^{q_{2}} \times \dots$ 꼴로 소인수분해하면, $N$의 배수 중 완전제곱수가 되는 가장 작은 수는 $N$에서 $q_i$가 홀수인 $p_i$를 하나씩만 더 곱한 수이다.
Unrated
#constructive
모든 3*3 정사각형이 다음을 만족하도록 N*M 행렬을 출력해야 한다.
1. 십자가 모양에 1,2,3,4,5가 각각 하나씩 있어야 한다.
2. 중앙을 제외한 8개의 칸에는 1,2,3,4,5가 모두 존재해서는 안 된다.
노트에 이것저것 막 그려보다가 어쩌다보니 정답을 찾았다. $i$행에 $2i-1$부터 1씩 증가하도록 출력해주면 된다. 모든 수는 1~5가 되도록 적절히 modulo 연산을 해주자.
Silver 3
#implementation
수열 시프트 연산은 단순히 a_i의 위치만 바꿔준다. 수열 시프트의 총 횟수를 저장하는 변수만 관리해서 해결할 수 있다.
Silver 1
#implementation #gcd
행, 열 별로 연속된 개수를 전부 gcd해주면 된다. 답이 1*k혹은 k*1인 경우는 예외로 처리해주자.
Gold 2
#disjoint_set #floyd_warshall #sorting
플로이드-워셜로 모든 정점에서의 최단거리를 구해주고 분리 집합으로 같은 컴포넌트에서의 최단거리 최댓값이 최소가 되는 점을 하나씩 뽑아서 정렬 후 출력하자.
Diamond 5
#miller_rabin_primality_test #pollard_rho
$n$이하의 수 중 $n$과 서로소인 수의 개수를 구하는 문제다. $n$을 소인수분해해서 $\phi(n)$을 구하자.
Platinum 1
#miller_rabin_primality_test #pollard_rho
웰노운이 되어버린 밀러-라빈 소수 판별 + 폴라드 로 알고리즘이다. 폴라드 로의 시간복잡도는 소인수분해하려는 수의 가장 작은 소인수 $p$에 대해 $O(\sqrt{p})$정도라고 한다.
Diamond 5
#miller_rabin_primality_test #pollard_rho
$N$의 약수의 개수를 구하자.
10/25
Gold 3
#constructive
Text 제출이 가능해 정답을 적진 않겠다. 두 선의 기울기가 최대한 비슷해지도록 배치해보자.
Gold 2
#meet_in_the_middle #binary_search
다트를 최대 4개 던졌을 때 획득할 수 있는 점수를 naive하게 구하면 $O(N^4)$으로 시간 초과를 받는다. 따라서, 다트를 최대 2개 던졌을 때 획득할 수 있는 점수를 naive하게 구한 뒤, 그 목록에서 임의의 두 수 $p, q$를 더 하면 4개를 던졌을 때의 점수를 얻을 수 있다. $p$값이 고정되어있다면 $p+q$가 m을 넘지 않게되는 최대의 $q$값은 이분 탐색으로 쉽게 구할 수 있다. 가능한 $p$는 $O(N^2)$개이므로 전체 시간복잡도 $O(N^2 \log{N^2})$로 시간 안에 해결할 수 있다.
던질 수 있는 다트가 4개라는 점에서 meet in the middle을 떠올리기 쉬웠다. mitm 기본 문제라고 봐도 무방할 듯 하다.
Platinum 2
#geometry #divide_and_conquer #sweeping
두 점 사이의 거리 중 가장 짧은 것을 구해주자. 이와 매우 비슷한 유명한 문제가 이미 존재한다.
내 풀이를 간략하게 설명하자면, 먼저 점을 정렬해주고 분할 정복을 수행했다. 현재 가지고 있는 점들 중 절반은 왼쪽, 절반은 오른쪽에 있도록 경계를 나누면, 거리가 최소가 되도록 하는 두 점이 나오는 경우는 다음 세 가지 중 하나이다.
1. 왼쪽 영역의 두 점
2. 오른쪽 영역의 두 점
3. 왼쪽 영역의 한 점 + 오른쪽 영역의 한 점
3번을 처리하는 것이 관건이다. 이걸 처리해야 쪼개놓은 두 구간을 합칠 때 위의 값들을 모두 구해줄 수 있다. (오른쪽 점의 x좌표) - (왼쪽 점의 x좌표) 가 현재 최솟값보다 더 작은 모든 점들에 대해 거리를 계산해서 최솟값을 구할 수 있다.
BOJ 20132 - Parity Constraint Minimum Spanning Tree
Diamond 5
#mst #hld #segtree
MST를 먼저 구해주고 시작하자. 이후, MST에 사용되지 않은 간선들을 하나씩 뽑아서 해당 간선이 포함된 MST의 가중치 값을 계산해주자. 추가되는 간선이 잇는 두 점을 $a,b$라고 하면, 기존 MST상에서 $a,b$를 잇는 단순 경로에 존재하는 간선 중 하나를 반드시 끊어야 한다. 이 때, 가중치 값이 가장 큰 간선을 빼줘야 새 MST의 가중치가 작아지므로 hld와 max segment tree로 경로에서의 최댓값을 관리하자. 단순히 하나의 max값으로만 판별하면 홀or짝의 최솟값 갱신이 제대로 이루어지지 않을수도 있다(예제 3을 참고). 따라서 segment tree에 홀, 짝 각각의 최댓값을 관리하면 된다.
10/26
Platinum 5
#dijkstra #set
다익스트라를 계~속 돌리면서 최단 경로에 포함되는 간선들을 지워주자. $N$ 제한이 작아서 충분히 돌아간다.
Platinum 3
#lca
최초의 루트를 $r$이라 하면, $tax(i) = sub(i)$와 같다. 만약 현재의 루트가 $v$이고, 찾으려는 tax의 점을 $x$라 하자. $v$가 $x$의 서브트리 내에 있지 않다면, 답은 단순히 원래의 $tax[x]$이다. 만약 $v$가 $x$의 서브트리 내에 있는 경우, $v$에서 $x$로 가는 경로 중 $v$ 다음의 점을 $g$라고 하면 답은 $($전체 점의 개수$) - tax(g)$이다. 예외로, $v=x$인 경우는 따로 처리해주었다.
Platinum 3
#lca #tree_dp
경우의 수 나누기는 위의 Sky Tax 문제와 같다. $x$의 자식들을 $c_i$라고 할 때, $x$를 LCA로 가지려면 $c_i$ 서브트리, $c_j$ 서브트리에서 하나씩 점을 고르거나 둘 중 하나가 $x$인 경우이다. 이를 이용해 dfs로 dp배열을 채우고, lca를 가지고 case work하여 dp배열의 값을 적절히 사용하자.
10/28
오랜만에 BOJ에서 열린 공개 대회에 참가했다. 약 한 시간 조금 넘게 풀었고, 7솔을 달성했다. 8번째 문제를 풀다가 헛다리를 계속 짚고 벽에 막혀 도망갔다.
04:21 AC
if문으로 특정 알파벳 찾는 문제다.
04:24 WA 04:25 AC
이것도 알파벳 찾는 문제지만 좀 더 까다롭다. 개수를 잘못 처리해줘서 한 번 틀렸다.
04:27 AC
처음부터 보면서 오리가 우는 시각을 최대한 한 번의 박수로 커버하면 된다.
04:46 WA 04:52 WA 04:54 AC
처음과 끝 전시만 보면 된다. 정렬해서 거리 합이 제일 작아지는 점을 찾으면 된다.
04:59 AC
0 XOR 3, 1 XOR 2의 값이 3으로 제일 크다. 이 두 가지 연산을 먼저 가능한 만큼 수행하고 남은 수들로 XOR을 더 해주면 된다.
05:17 AC
'웅크리기'와 '네발로 걷기'만 고려한다면 $O(2^N)$ 브루트포스이다. 여기에 추가로 '깜짝 놀라게 하기'를 사용하는 경우엔 다음 턴에 받는 데미지가 0이기 때문에 무조건 '네발로 걷기'를 사용하는 것이 이득이다. 그렇게 두 턴을 건너 뛰어주면 된다.
05:22 WA 05:23 AC
수 $N$을 나누면 $\lfloor \frac{N}{2} \rfloor$와 $\lceil \frac{N}{2} \rceil$로 나뉜다. 각각 $L, R$로 놓고 $L, R$을 반 씩 계속 쪼개서 왼쪽 끝 값과 오른쪽 끝 값을 유지하자. 만약 $L \le M \le R$인 순간이 있다면 답은 YES이다.
$M = 1$와 $M = N$인 경우 예외 처리를 안해줘서 한 번 틀렸다.
10/29
Silver 3
#bruteforcing
길이가 짝수인 회문 수, 홀수인 회문 수를 직접 모두 구해주면 된다. 개수가 그리 많지 않다.
Silver 2
#priority_queue
최소 힙에 원소들을 넣으면서 사이즈가 $N$을 넘지 않게 관리해주자.
Silver 2
#string
주어진 문자열을 A라 하면 $1\le i < N$인 모든 $i$에 대해, substr(i, A.size()-i)와 A의 각 자리가 모두 동일한지 검사한다.
모두 같다면, A에 $i$초 후에 부른 노래로 문자열을 추가한다.
Gold 4
0번째는 $M$에서 시작한다. $i$번째 문제를 풀 때에, $i+1$번째에 도달할 수 있는 차원을 모두 가지고있으면 된다.
naive하게는 $2^N$개이나, $\bmod N$의 값만 관리하므로 최대 $N$개만 관리해주면 된다.
10/30
Gold 5
#bruteforcing
등차수열이 되도록 처음 두 항을 골라놓고 재귀로 완전탐색해주면 된다. 한 자리의 경우는 미리 처리하자.
Gold 5
#simulation
only 시뮬레이션이다. 도미노를 넘어뜨리는 행위를 재귀함수로 만들면 구현이 편해진다.
Gold 5
#graph #string
$O(N^2)$으로 각 문자열 사이에 간선을 만들어준다.
구체적으로, 문자열 $S$에 한 글자를 끼워서 $E$를 만들 수 있으면 $S$에서 $E$로 가는 단방향 간선을 만들어준다.
시작점에서 갈 수 있는 곳 중 가장 길이가 긴 문자열을 아무거나 출력해주자.
Gold 4
#gcd
$(0,0)$와 $(a,b)$를 잇는다고 가정하자.
$a = 1, b = 1$이 아니면, $\gcd(a,b) = 1$이어야만 둘 사이를 이을 수 있다.
${L_1}^2 \le a^2 + b^2 \le {L_2}^2$이면 $(0,0)$와 $(a,b)$를 이을 수 있고, 각 점들을 $(x,y)$만큼 이동시키는 경우도 둘 사이를 이을 수 있다.
이 때 나올 수 있는 모든 경우의 수는 $(W-a+1)\times(H-b+1)$이고, 상하 반전된 경우도 고려해야 하므로 여기에 $\times 2$를 해줘야 한다.
$1 \le a \le W, 1 \le b \le H$인 모든 경우에 대해서 값을 구해 더해주면 된다.
예외로, $a$나 $b$가 $0$인 경우는 $L_1 = 1$인 경우에 한해서 성립할 수 있으므로 따로 처리해주자.
Gold 3
#math
이 문제와 유사한 듯 하다. 길이가 $\sqrt{D}$인 선분으로 $(0,0)$와 $(x,y)$를 이으려면 몇 개를 써야할까? 라는 문제이다.
$(x,y)$까지의 거리를 $\sqrt{D}$로 나눠주고 나누어 떨어지지 않으면 1을 더해 출력해주면 되지만, $\sqrt{D}$가 더 긴 경우는 1회만에 갈 수 없기 때문에 예외처리 해주어야 한다.
30분 챌린지 중이었는데 예외처리를 안해줘서 계속 맞왜틀하고 있었다ㅠㅠ
10/31
Gold 4
#priority_queue #bfs
문제의 요구 사항을 그대로 구현하다보면, 자연스레 PQ + bfs가 된다.
Gold 4
#dp
$dp[i]$를 $i$번 정비소에서 정비를 받는 경우의 답이라고 정의하면, $O(N^2)$에 해결할 수 있다. 경로 추적은 2차원 벡터로 해당 점에서 정비를 할 때 거친 점들을 모두 저장하는 식으로 해줬다.
Gold 3
#knapsack #graph_traversal
그래프 탐색으로 그룹 별 {아이들 수, 사탕의 합}을 구해서 knapsack dp로 해결할 수 있다. knapsack dp를 제대로 해본 적이 없어서 WA를 많이 맞았다. 이번 기회에 제대로 배워가는 것 같다.
Gold 4
#bruteforcing #implementation
회전 연산을 구현하고 next_permutation으로 나올 수 있는 모든 회전 연산 순서의 결과 중 최솟값을 구해주면 된다.
Gold 3
#priority_queue #bfs
바닥을 제외한 외곽의 광물을 모두 최소 힙에 넣고 bfs를 수행해서 K개의 광물을 뽑아내면 된다.
BOJ 17193 - I Would Walk 500 Miles
Gold 2
#math #ad_hoc
$i$와 $j$를 잇는 거리는 $i$가 같을 때, $j$가 늘어날수록 줄어든다. 또한, $j$가 같을 때 $i$가 늘어날수록 줄어든다. 따라서 최대가 되는 $M$을 구하려면 $K-1$개의 그룹에 $1, 2, \cdots$를 넣어야 하고, 한 개의 그룹에 나머지를 모두 넣어주면 된다.
Gold 2
#dp #graph
스키는 항상 높은 곳에서 낮은 곳으로만 탈 수 있다는 조건에 의해 dp 식이 깔끔하게 짜여진다. $dp[i][j]$를 $i$번 지점까지 리프트를 $j$번 타고 왔을 때의 최대 시간으로 정의하고 풀면 된다.
Gold 1
#bellman-ford #graph_traversal
최적의 경로가 존재하려면 반드시 $1$에서 $n$으로 갈 수 있어야 한다. 또한, 양의 가중치를 갖는 사이클이 존재해서는 안 된다.
가중치에 -1을 곱해서 생각하면, 음수 가중치가 존재하는 그래프에서의 최단 경로를 찾는 문제로 변한다.
벨만-포드 알고리즘을 사용하면 음의 사이클 판별 + 최단 경로까지 구할 수 있다.
맞왜틀을 많이 당했는데, 음의 사이클이 있더라도 그 사이클에서 $n$까지 가는 길이 없다면 최단 경로에 영향을 주지 않는다는 사실을 간과했다.
'문제 풀이' 카테고리의 다른 글
| 11월의 문제 풀이 - (2) (2) | 2023.11.21 |
|---|---|
| 11월의 문제 풀이 - (1) (0) | 2023.11.11 |
| 10월의 문제 풀이 - (2) (0) | 2023.10.21 |
| 10월의 문제 풀이 - (1) (1) | 2023.10.12 |
| 9월의 문제 풀이 - (2) (1) | 2023.10.03 |