9월의 문제 풀이 - (1)
9/11 ~ 9/20에 푼 문제들입니다.
문제의 풀이에 대한 스포일러가 포함되어있습니다.
9/11
Gold 1
#divide_and_conquer
postorder로 방문한 마지막 정점이 트리의 루트임을 이용해서 루트 기준으로 왼쪽 서브트리, 오른쪽 서브트리에 대해 각각 루트를 구해주는 방식으로 해결할 수 있다.
Gold 3
#mst
mst에서 이미 연결된 간선들이 주어지는 것 이외에는 기본 mst 문제와 같다.
Gold 4
#mst
mst의 가장 기본적인 문제이다.
Gold 3
#stack
{각 수가 등장한 횟수, 인덱스} 쌍으로 stack에 차례대로 넣으면서 오등큰수를 찾아주자.
BOJ 29736 - 브실이와 친구가 되고 싶어 🤸♀️
Bronze 4
구간 $[k-x, k+x]$에 속한 모든 정수 중 a이상 b이하인 수들의 개수를 세주자.
Bronze 4
if문을 사용하자.
Bronze 3
날짜를 하나의 정수로 치환할 수 있다.
Bronze 3
원소의 개수를 직접 세면서 꽉 찼으면 $2$를 곱해주면 된다.
Bronze 3
음수가 나오는 경우만 잘 처리해주면 된다.
BOJ 29724 -🍎📦 '사과상자'에 들어있는 것은 무엇? 현금?
Bronze 1
사과상자에 들어있는 사과의 수는 $\frac{W}{12} \times \frac{H}{12} \times \frac{L}{12}$개이다.
Silver 4
#combinatorics
(전체 경우의 수) - (브실이가 불침번 근무를 아예 서지 않는 경우)를 구하자.
Silver 3
#prefix_sum #sliding_window
열 누적합 배열의 누적합에서 구간 A의 합이 가장 큰 것을 구하자.
Silver 3
#string #sorting #parsing
getline으로 학습 기록을 읽고, "boj.kr/"로 시작하는 문자열이면 따로 문제 번호를 저장한다.
입력이 끝나면 정렬해서 출력해주자.
BOJ 29721 - 변형 체스 놀이 : 다바바(Dabbaba)
Silver 4
#set
입력으로 들어오는 점에 인접한 4개의 점들 중 이미 다른 기물이 있거나 맵을 벗어나지 않으면 그 점은 항상 갈 수 있는 곳이다.
set으로 관리해주면 편하다.
Silver 3
#combinatorics
$a$가 $0$인 쿼리의 개수를 $g$, $0$이 아닌 쿼리의 개수를 $f$라고 하면, 최대 시도 횟수는 $ _{N-f}P_{g} \times _{9-f-g}P_{N-f-g}$이다.
Silver 2
#map #set #simulation
map과 set을 이용해 직접 simulation하자.
Gold 4
#sorting #implementation
문제에서 제시된 우선순위대로 정렬함수를 구현하자.
9/12
Gold 5
#greedy
식을 전개하면 $A[e] - A[s] (e-s \ge N-M-1)$의 최댓값을 찾는 문제임을 알 수 있다. $e$를 $N-M$부터 $N$까지 옮겨가면 $s$로 가능한 범위도 $1$에서 $1+M$으로 늘어난다. 이 때 $A[s]$가 작아지면 새로 $s$를 갱신해주면 된다.
BOJ 29728 - 실버와 소수는 둘다 S로 시작한다
Silver 2
#sieve_of_eratosthenes #deque #simulation
$1$부터 $N$까지 직접 simulation하면 된다. 뒤집는 연산을 덱의 push방향을 바꾸는 것으로 대체하자.
Silver 2
#math
주어진 선분이 축에 평행하지 않다면 새로 만들어지는 직사각형은 없다. 그렇지 않은 경우에는 선분의 길이와, 평행한 축 기준으로 up, down 혹은 left, right에 존재하는 선의 개수를 구해서 추가되는 직사각형의 수를 계산하면 된다.
Silver 2
#binary_search
가능한 레벨을 $[1, 10^{9}]$내에서 등차수열 합 공식 + 이분 탐색으로 구해주자.
Silver 4
설명할 것이 없다. 주어진 대로 only 구현
Silver 5
#set #priority_queue
수강하지 않는 과목들을 모두 최대 힙, 최소 힙에 넣고 각각 $M-K$번 pop하여 최소, 최대 점수를 구하자.
Bronze 1
R이 입력될 때마다 R 위치를 기준으로 K만큼 떨어져있는 사람들을 감염시켜주면 된다. 간단한 식으로 $O(N)$에 해결할 수도 있다.
Bronze 1
시간을 정수로 치환한 후에 계산하면 된다.
Bronze 2
B가 두 개 있어도 R이 하나밖에 없으면 "BR"은 하나밖에 만들지 못한다. 이 규칙을 "BRONZESILVER"에 적용해 풀면 된다.
Bronze 2
입력 한 줄을 정수로 바꿔주고 J보다 작거나 같은 수의 개수를 세어주자.
Bronze 2
집에서 공부를 하는 경우, 독서실에서 공부를 하는 경우 두 가지 뿐이다. 각각의 시간을 계산해서 작은 쪽을 출력하자.
Bronze 4
흑의 기물 점수를 음수로 취한 뒤, 체스판에 존재하는 모든 기물의 합을 출력하자.
Bronze 5
여러 문장을 입력받아 주어진 목록에 속하는 지 여부를 모두 AND연산 해준 값이 TRUE이면 "Yes", 아니면 "No"이다.
Silver 3
#binary_search
$1\le i \le N$인 $i$에 대해 $S - A_{i}$의 개수를 upper_bound와 lower_bound를 이용해 구해서 모두 더한 값이 답이다.
Unrated
#bruteforcing
'?'의 자리에 모든 기호를 한 번씩 넣어본다.
9/14
Platinum 4
#greedy
어떤 구간에 양수는 하나만 있는 것이 최적이라는 사실은 쉽게 볼 수 있다. 여기서 생각을 조금 넓혀서, 어떤 구간에 양수 하나와 최대한 많은 양 옆의 음수들을 집어넣자.
9/17
Diamond 5
#greedy #math #constructive
집합의 maximum cardinality는 항상 $ \frac{N+1}{2}$이다. 어떤 수는 자신보다 적어도 두 배 이상 작은 수에 의해서만 나누어지기 때문에, $\lfloor \frac{N}{2} \rfloor + 1, \cdots, N$까지의 수의 집합은 amazing하다. 자세한 증명은 모르지만, 초기 집합을 $1$부터 $N$까지의 홀수로 하고 interesting set의 조건을 만족하도록 구성하다보면 특별한 규칙을 찾을 수 있다. 테스트 케이스당 $O(\log_{3}{N})$에 해결이 가능하다.
9/18
Silver 3
#map #bruteforcing
map에 각 string의 index를 저장해두고, $i<j$이면서 $M[string[i]]<M[string[j]]$인 ${i,j}$ 쌍의 수를 구하자.
BOJ 11974 - Subsequences Summing to Sevens
Gold 5
#prefix_sum
어떤 구간 $[a,b]$에 대해 $A_{a}+\cdots+A_{b}$가 $7$의 배수라면, $A_{1}+\cdots+A_{a-1}$를 $7$로 나눈 나머지와 $A_{1}+\cdots+A_{b}$를 $7$로 나눈 나머지가 같다는 것을 이용한다. prefix sum이 $i (0\le i<7)$가 되는 구간의 최장 길이를 저장하자.
Gold 5
#pigeonhole_principle #bruteforcing
$N$이 $10,000$보다 큰 경우에도 존재하는 수의 종류는 항상 $10,000$개 이하이다. counting 배열을 이용해서 $10,000 \times Q$에 해결하자.
Platinum 4
#dfs #lca
루트가 매번 달라지므로 일단 $1$번을 루트로 가정하자. $v$번 정점의 score는 $v$를 루트로 갖는 서브트리의 모든 score의 합이다. 이는 dfs 한 번으로 쉽게 구할 수 있다. 만약 $r$이 루트일 때 $v$의 score가 변하려면, $r$이 $v$를 루트로 갖는 서브트리 내에 존재해야 한다. 이 경우에는 $r$과 $v$를 잇는 경로에서 $v$ 바로 다음의 정점을 $u$라고 하면, $v$의 score는 ($1$의 score) - ($u$의 score)이다.
Platinum 2
#dfs #constructive
직관적으로 봤을 때 리프 노드(차수가 1인 노드)들끼리 이어줘야 한다는 것은 쉽게 유추할 수 있다. 잇는 방법은 단순히 dfs탐색 순서 기준으로 $\frac{N}{2}$ 이상 차이나는 노드들끼리 이어주면 된다.
Platinum 1
30028번과 동일하나, 루트가 입력으로 들어온다.
9/19
Platinum 5
#tree #dfs
정점 $v$를 지나는 모든 단순경로를 생각해보자. 루트를 $1$번 정점으로 잡았을 때, $v$를 루트로 갖는 서브트리 내의 한 정점 $b$를 도착점으로 갖고, 이 서브트리에 포함되지 않는 한 정점 $a$를 시작점으로 생각하면 $a$에서 $b$로 가는 모든 경로가 $v$를 포함하게 된다. 마찬가지로 $b$에서 $a$로 가는 경로 또한 $v$를 포함한다. 즉, 각 정점 별 서브트리의 노드 개수만 알면 답을 구할 수 있다.
Silver 1
#geometry #euclidean_algorithm
S와 E가 속한 구간의 선분의 방정식을 이용해 $y$좌표를 구해주고 두 점의 기울기를 계산해주면 된다. 이 때 모든 계산은 long long타입의 (분자)/(분모) 형태로 계산되어야 한다. 통분하는 과정에서 GCD가 필요하다.
Gold 3
#primality_test
지문을 대충 읽고 예제 출력으로 답을 유추해서 풀었다. N이하의 가장 큰 소수를 구하면 된다.
9/20
Gold 3
#map #bruteforcing
나무젓가락 2개의 순서쌍으로 가능한 모든 경우를 $O(N^{2})$에 탐색해서 길이 $20,000,001$의 배열에 합 별로 가능한 최대 넓이를 구하면 된다.