10/1 ~ 10/10에 푼 문제들입니다.
문제의 풀이에 대한 스포일러가 포함되어 있습니다.
잘못된 풀이가 있다면 지적해주세요.
10/2
Gold 5
#prefix_sum
imos법으로 알려져있는 걸로 알고 있다. 구간의 변화를 시작점과 끝점에 각각 +1, -1을 취하는 방법인데, 이 문제에선 반대로 -1, +1을 해주면 된다.
Gold 4
#greedy
만약 $a_{i}$가 $K$보다 작다면, 무조건 가까운 곳에서 끌어오는 것이 이득이다. 끌어오는 쪽의 $a_{i}$가 $K$보다 작아도 무조건 끌고 오는 것이 포인트이다. 아이디어는 금방 떠올랐지만 개인적으로 구현이 힘들었다.
10/3
Platinum 5
#mst #lca
만들어질 수 있는 스패닝 트리에서 가장 큰 간선의 가중치만 음수로 취했을 때의 스패닝 트리 가중치 합의 최솟값을 구하는 문제이다.
먼저 주어진 그래프에서 mst를 구하자. 이것을 $G$라 하고, 가중치의 합을 $S$라고 하자. 모든 간선에 대해 해당 간선 가중치를 음수로 취했을 때의 mst를 계산해주었다. 원래의 mst를 $G$라고 하고, 현재 검사하려는 간선을 $E$라고 하자. $E$가 $G$에 포함되어 있다면 단순히 $S - 2 \times weight(E)$가 된다. 포함되어있지 않다면 조금 복잡해진다. $E$가 연결하는 두 정점을 $a,b$라 하고 가중치를 $v$라 하면, $G$에서 $a$와 $b$를 잇는 단순 경로 상의 max weight을 $max$라고 하면, $S - max - v$가 된다. 이들의 최솟값을 구해주면 된다.
10/5
Bronze 3
#bruteforcing
$1$부터 $N$까지 직접 박수 횟수를 계산해주면 된다. 정수를 문자열로 변환해주는 to_string 함수가 많이 도움되었다.
10/8
Bronze 2
#ad_hoc
만약 2개 이상의 그룹이 분배 기준을 만족한다면, 모두 하나의 전체 그룹으로 합칠 수 있다. 대우 명제는 "전체 그룹이 분배 기준을 만족하지 않으면, 2개 이상의 그룹이 생길 수 없다."이다. 따라서 모든 $p_{i}$의 합이 $X$로 나누어떨어지면 답은 1, 아니면 0이다.
Silver 2
#sorting #greedy
주어지는 전투력은 모두 양수이므로 전투력을 최대한 늘리려면 곱하기 아이템의 사용을 최대한 늦춰야한다.
Gold 4
#bfs #combinatorics
시작점으로부터 $i$만큼 떨어진 정점의 수를 $cnt_{i}$라 하고, $i$만큼 떨어진 정점까지 고려했을 때의 총 경우의 수를 $ans_{i}$라고 하자. $ans_{i} = ans_{i-1} + (ans_{i} + 1) \times cnt_{i}$이고, 시작점에서 가장 멀리 떨어진 점까지의 거리를 $d$라 하면 답은 $ans_{d}$이다.
10/10
Silver 1
#bruteforcing
$N$이상의 수 중 이진수로 변환했을 때의 1의 수가 $K$보다 작은 가장 작은 수를 출력하자. 관찰해보면 답은 항상 $N$보다 작기 때문에 브루트포스로도 통과한다.
Platinum 4
#math #ad_hoc #simulation #offline_query #priority_queue
특정 날짜가 지나면 수열이 모두 같은 수가 되거나 $a, a, b, b, ..., b$처럼 될 때가 있는데, 이 날짜를 $day$라고 하자. 초기 $a_{i}$의 값이 30보다 작기 때문에 $day$의 값이 그렇게 크지 않을거라는 관찰이 필요하고, 직접 시뮬레이션하며 구하면 된다. 쿼리를 모두 받아 날짜 순으로 정렬하고 오프라인으로 처리하자. 현재 쿼리를 ${d, n}$이라 할 때 만약 $d \le day$이면 시뮬레이션으로 구하고 $d \ge day$이면 수식으로 구할 수 있다.
Platinum 4
#greedy #sorting #bigint
만약 수 $a$가 정수인 $b,c$에 대해 $b \times c$로 표현될 수 있다면, 무조건 $a$를 빼고 $b,c$를 넣는 것이 이득이다. $b, c$를 최적으로 붙였을 때 항상 $a$보다 커지기 때문이다. 자연스럽게 최대한 많은 수로 분해해야 한다는 것을 알 수 있고, $N$을 소인수분해하면 된다. 소인수분해한 수들을 이어붙여야 하는데, $b, c$를 이어붙일 때 $bc$가 더 큰지 $cb$가 더 큰지에 따라 정렬함수를 구현해서 정렬해주면 된다. 이제 $M$을 최적으로 골라 똑같이 소인수분해하는 일만 남았다. $M$값은 $N$보다 작으면서 $2^{i}$ 혹은 $2^{i} + 2^{i-1}$꼴을 만족하는 가장 큰 수가 된다. 수들이 long long 범위를 넘어가기 때문에 문자열로 변환해서 더해주었다.
끝
'문제 풀이' 카테고리의 다른 글
| 10월의 문제 풀이 - (3) (1) | 2023.11.01 |
|---|---|
| 10월의 문제 풀이 - (2) (0) | 2023.10.21 |
| 9월의 문제 풀이 - (2) (1) | 2023.10.03 |
| 9월의 문제 풀이 - (1) (0) | 2023.09.27 |
| BOJ 10830 : 행렬 제곱 [C++] (0) | 2023.02.18 |