12/1 ~ 12/10에 푼 문제들입니다.
문제의 풀이가 포함되어있으니 유의하세요.
12/1
BOJ 1911 - 흙길 보수하기
Gold 5
#sorting #greedy
웅덩이들을 $x$좌표 기준 오름차순으로 정렬해놓고, 변수 $t$를 (마지막 널빤지가 덮고있는 끝 지점 +1)로 유지하며 관리하자.
어떤 웅덩이 $[S, E)$에 대해, 그 웅덩이를 모두 덮기 위해 필요한 널빤지 수는 다음과 같다.
$\lfloor \dfrac{E - \max(t, S) - 1}{L} \rfloor + 1$
단, 마지막 널빤지가 그 웅덩이 전체를 포함하는 경우는 예외다.
BOJ 30037 - K-Words Problem
Gold 3
#implementation #string
문장 하나를 getline으로 받아서 2번 규칙을 가능한 만큼 모두 적용시켜주고, 그 다음 1번 규칙을 모두 적용시키면 된다.
(그냥 깡 구현 문제다.)
BOJ 2423 - 전구를 켜라
Gold 1
#dijkstra
각 꼭짓점을 정점으로 보면, 각 칸에 주어지는 문자는 비용이 0인 간선으로 볼 수 있다.
그 칸에 90도 돌린 간선을 비용 1로 두고 추가한 뒤에, (0,0)에서 다익스트라를 돌리면 된다.
BOJ 2143 - 두 배열의 합
Gold 3
#binary_search #prefix_sum
각 배열에서 부분 합으로 가능한 모든 수를 $AA, BB$ 벡터에 담아놓자.
$BB$를 정렬시키면, $AA$에서 한 원소를 골랐을 때 $BB$에서 가능한 값들의 개수는 이분 탐색으로 구할 수 있다.
BOJ 14572 - 스터디 그룹
Platinum 5
#sorting #greedy
문제에서 제시한 효율성의 식을 현재 그룹에 대한 정보와 함께 다음과 같이 나타내보자.
$E_{now} = (A_{now} - B_{now}) \times C_{now}$
여기에 실력차이가 $D$이상 나지 않는 어떤 사람을 넣었다고 가정해보자.
인원을 뺀 게 아니기 때문에 $A, B$의 값은 절대 줄어들 수 없다. $A, B$가 증가한 양을 각각 $a, b$라고 하자.
$E_{next}$가 $E_{now}$ 이상이어야 함은 곧 아래와 같은 식으로 정리할 수 있다.
$a - b \ge \dfrac{B_{now} - A_{now}}{C_{now}+1}$
여기에서, 좌변은 항상 $0$보다 작을 수 없고 우변은 항상 0보다 클 수 없다.
따라서, 넣을 수 있을 만큼 그룹에 인원을 많이 넣는 것이 항상 최적이다.
12/2
BOJ 2180 - 소방서의 고민
Platinum 5
#sorting #greedy
주어진 쌍 중 어떠한 두 쌍 $P = (a_1, b_1), Q = (a_2, b_2)$에 대하여, 무엇을 먼저 처리해야 최적인지 생각해보자.
현재까지 걸린 시간이 $t$일 때, $P \rightarrow Q$와 $Q \rightarrow P$의 순서로 처리했을 때의 시간 $t_1, t_2$를 각각 새로 계산해보자.
$t_1 = t + a_1(t + a_2t) + a_2(t + b_1) + b_1 + b_2$
$t_2 = t + a_2(t + a_1t) + a_1(t + b_2) + b_1 + b_2$
$P$가 먼저 와야 하는 경우는 $t_1 < t_2$인 경우이고, 식을 정리하면 다음과 같이 간단히 정리된다.
$a_2b_1 < a_1b_2$
만약 $t_1 = t_2$라면, $a_1, a_2$중 더 큰 값을 가진 쪽을 먼저 가야하고, $a_1 = a_2$라면 $b_1, b_2$중 더 큰 값을 가진 쪽을 먼저 가야한다.
12/3
BOJ 14033 - Artskjid
Gold 1
#bitmask_dp
$dp[i][j]$를 다음과 같이 정의하고 Top-Down으로 풀면 된다.
- $j$는 정점들의 방문 여부를 이진수로 압축한 정수이고, $i$번 점을 마지막으로 방문했을 때의 최댓값
12/4
BOJ 1264 - 모음의 개수
Bronze 4
#string
getline으로 한 문장씩 입력받아, 모음이 존재하는지 확인한다.
check = "aeiouAEIOU"로 놓고 한 글자마다 for문으로 검사했다.
BOJ 2171 - 직사각형의 개수
Gold 5
#set
주어진 점들의 어떤 쌍 $(x1, y1), (x2, y2) (x1 \neq x2, y1 \neq y2)$에 대해, $(x1, y2)$와 $(x2, y1)$이 존재하는 지 확인하면 된다.
set이나 map으로 점의 존재 여부를 $O(\log{N})$에 알 수 있다. 전체 시간복잡도는 $O(N^2\log{N})$이다.
좌표 압축을 이용하면 $O(N^2 + N\log{N})$에도 해결할 수 있을 것 같다.
BOJ 15709 - 정기검진
Platinum 5
#dijkstra
집에서 병원으로 가려면, 중간에 반드시 다리를 거쳐야 한다고 문제에 대놓고 써있다.
$S_i$에서 $E_i$로 가는 도중 거치는 다리를 $B_i$라고 하면, 양방향 도로이므로 $S_i \rightarrow B_i \rightarrow E_i$의 경로는 $(B_i \rightarrow S_i) + (B_i \rightarrow E_i)$로 나타낼 수 있다.
다리의 수는 최대 100개밖에 되지 않으므로 100번 다익스트라를 돌려서 각 다리에서 출발했을 때의 최단 경로들을 저장하면 된다.
하나의 쿼리마다, 각 다리를 지나는 경로의 개수인 $B$번만큼 검사해주면 된다.
$O(BK\log(N+M+B))$이고, 쿼리 처리는 $O(BQ)$에 가능하다.
BOJ 25608 - 장난감 섞기
Gold 1
#prefix_sum #divide_and_conquer #bruteforcing
각 수열마다 left, right, sum, total을 구해준 뒤, 구간 연속합 테크닉(?)으로 전체 수열에서 연속합을 구해줬다.
next_permutation으로 $10!$가지 경우를 모두 돌리면 된다.
BOJ 6764 - Sounds fishy!
Bronze 4
"if문의 사용법을 알고있는가?" 라는 문제이다.
출력 문자열에 주의해야 한다.
BOJ 2481 - 해밍 경로
Gold 2
#bitmask #map #bfs
해밍 경로가 1이라는 것은 어떤 수 $P$에서 비트 한 개만 바꿔준 것이기 때문에 경우의 수는 총 $O(K)$가지이다.
입력으로 들어온 모든 이진 코드에 대해, 해밍 경로를 통해 서로 오갈수 있는 관계를 그래프로 형성해줬다. 시간복잡도는 $O(NK)$이다.
$M$번의 질의가 주어질 때마다, bfs로 최단 경로를 찾아주고 방문 배열로 역추적해서 경로를 구해줬다.
시간복잡도는 $O(NKM)$이다.
12/5
BOJ 1035 - 조각 움직이기
Gold 1
#bfs
조각의 위치로 가능한 가짓수는 $25$이다.
조각이 최대 5개까지만 주어지므로, 총 $25^5$가지의 상태가 등장할 수 있다.
5차원 배열로 bfs를 돌리자.
BOJ 13701 - 중복 제거
Gold 4
#bitset
가능한 수의 범위만큼의 비트 집합을 관리하자.
BOJ 2314 - 이세계 게임
Gold 3
#bfs #bitmask
4X4 행렬을 정수로 변환할 수 있다. 모든 가능한 행렬의 경우의 수는 $2^{16}$가지이고, 이것을 상태로 가지는 bfs를 수행하면 최단 시간을 찾을 수 있다.
12/7
BOJ 30094 - 그래서 나는 사진을 그만두었다
Gold 2
#greedy #sorting #combinatorics
어떤 두 쌍 $I = (c_i, a_i), J = (c_j, a_j)$가 있을 때, 무엇이 왼쪽에 와야 점수가 최소일까?
가능한 순서 $(I, J), (J, I)$의 점수를 비교하여 최소일 때를 구해보자.
정리하면, $a_i - c_i < a_j - c_j$일 때, $I$가 왼쪽에 와야 최소가 된다.
반대로 생각하면, 해당 경우에 $I$가 오른쪽에 와야 최대가 됨을 알 수 있다.
가능한 가짓수는, $a_i - c_i = a_j - c_j$인 쌍이 등장할 경우에 발생할 수 있고, 그 값으로 같은 값을 가지는 쌍들의 개수를 $c$라고 할 때, 모든 $c$에 대해 $\prod {c!}$이 된다.
BOJ 3197 - 백조의 호수
Platinum 5
#bfs #disjoint_set
물 공간이 이루는 영역 하나에 각각 $1$부터 고유한 번호를 붙여주면, 빙판이 녹아감에 따라 두 $L$이 연결되는지의 여부는 bfs + 분리 집합으로 구해줄 수 있다.
BOJ 15403 - Escape Room
Platinum 5
#greedy #sorting #constructive
$a_i$가 각각 $1, 2, \cdots$인 $i$들에 대해, 오른쪽부터 $k ~ k+m$을 잘 배치하자.
BOJ 13132 - World Cup
Gold 4
#probability #bruteforcing
가능한 경우 $2^N$가지를 모두 확인하여, 만족하는 경우만 그 때의 확률을 더해주자.
BOJ 2515 - 전시장
Gold 2
#dp #sorting #binary_search
그림을 높이 순으로 오름차순 정렬한 뒤, 여기서 $i$번째 그림까지 배치했을 때의 가격의 최대 합을 생각해보자.
$i$번째를 반드시 마지막으로 포함하는 경우를 $dp[i]$로 생각해보면, $dp[i] = \max(dp[1], \cdots, dp[j]) + c_i$이다.
여기서 $j$는 $h_i - S \ge h_j$이면서 가능한 가장 큰 값이다.
모든 $dp$값의 최대를 출력해주면 된다.
12/10
BOJ 20093 - Coins
Platinum 3
#ad_hoc
만점을 받기 위해선, 동전을 최대 한 번만 뒤집을 수 있다. 어떠한 동전 배치가 나오던 간에.
보드에서 1인 곳의 label을 모두 xor해준 값을 $s$라고 하자.
$s \oplus m = c$를 만족하는 $m = s \oplus c$이므로, 우리는 $m$번째 동전을 뒤집어서 보내주고 받는 쪽에선 모든 1의 위치를 xor해주면 원하는 좌표를 찾을 수 있다.
문제의 제한이 큰 힌트가 되었다.
BOJ 17799 - Feeding Seals
Gold 5
#greedy #sorting #two_pointers
정렬해놓고 가장 큰 거와 가장 작은 거를 같이 먹을 수 있는지 확인하면 된다.
BOJ 18112 - 이진수 게임
Gold 5
#bfs
각 이진수로 bfs를 돌리면 된다.
BOJ 5567 - 결혼식
Silver 2
#graphs #set
친구 관계로 그래프 형성 후, 1의 친구와 1을 제외한 그의 친구들까지 모두 set에 넣고 set의 size를 구하면 된다.
'문제 풀이' 카테고리의 다른 글
| BOJ 14676 - 영우는 사기꾼? [C++] (0) | 2023.12.12 |
|---|---|
| BOJ 25685 - 좋은 노드 집합 찾기 [C++] (0) | 2023.12.12 |
| 11월의 문제 풀이 - (3) (4) | 2023.12.01 |
| 11월의 문제 풀이 - (2) (2) | 2023.11.21 |
| 11월의 문제 풀이 - (1) (0) | 2023.11.11 |