2024.03.25. ~ 2024.03.31.

백준 13 문제.
 
1. BOJ 17219 : 비밀번호 찾기 - S4
Hash map 문제.
그냥 Hash map에 주소값을 key로, 비밀번호를 value로 저장한 다음
각 쿼리별로 대답해주면 된다. 
 
2. BOJ 28705 : RLE Inversion Counting - P3
Math(Combinatorics) + Segment Tree + Value Compression 문제.
 
일단 값의 범위가 매우 크므로 값 압축은 당연히 필요하다.
그리고 지금 K번 이어붙이는 수열이 아닌 전에 이어붙인 수열과에서는 그냥 각 element 별로 inversion counting 결과값이 m_i이라면 m_i * K로 전부 더해주면 된다. 이는 Segment Tree로 가능하다.
 
그런데 이제 문제는 K번 이어붙이는 같은 수열 내부에서의 inversion counting인데, 두 가지의 경우의 수들을 살펴보아야 한다. 현재 i번째 element에 대하여

• i번째 element보다 앞에 있으면서 값이 더 큰 element의 개수가 j개라면 총 j * (K * (K+1) / 2)를 더하면 된다.
• i번째 element보다 앞에 있으면서 값이 더 작다면, 두 번째로 이어붙이는 경우에는 i번째 element가 더 앞에 있게 되므로 개수가 j라면 j * (K * (K-1) / 2)를 더하면 된다.

이를 Segment Tree 3개를 관리하는 방법으로 나는 풀었다. (사실상, 값 압축 Segment Tree 1개, PBDS 2개)
구현량이 비교적 많아 잠오는데 풀기 귀찮았다...
 
3. BOJ 5529 : 저택 - P4
Dijkstra + Implementation 문제.
 
각 스위치와 시작 및 끝나는 곳을 노드로써 생각을 해보면, 상하좌우로 이동시에 처음으로 만나는 노드끼리만 연결 + 간선의 비용 == 거리로 두어 가중치가 있는 그래프로 구성할 수 있다. (상하좌우로 이동가능한 모든 노드끼리 연결할 필요는 없다. 왜냐면 결국에는 근처에 있는 노드를 거쳐서 가기 때문에...) 또한, 현재 문제를 그러면 가중치가 존재하는 그래프에서 {1,1}에 해당하는 노드에서 {N,M}에 해당하는 노드까지의 최단거리 계산하는 문제가 된다.
 
그래서, 최단 거리를를 계산하는 배열을 상하로만 문이 열렸을 때와 좌우로만 문이 열렸을 때 따로 계산해서 Dijkstra를 돌리면 되는데, {1,1} 에도 스위치가 존재할 수 있으니 {1,1}는 스위치 여부에 따라서 스위치를 누른 상태를 계산할 지 따로 예외처리 해주면 된다.
 
구현이 까다로웠던 문제. 아이디어는 그래도 어느정도 빨리 생각해낸것 같은데... 최적화 및 구현이 어려웠다. 
 
4. BOJ 31631 : :rightplant: - G3
Ad hoc + Constructive 문제.
 
관찰을 통해서 i번째 빌딩에 대한 B_i는 왼쪽에 i번째 빌딩보다 높은 빌딩들의 높이 합 을 L_i, 오른쪽에 i번째 빌딩보다 높은 빌딩들의 높이 합을 R_i라고 하면 min(L_i, R_i)에 따라서 B_i가 정해지는 걸 알았다. 그래서 L_i와 R_i를 최대한 균등하게 맞춰주면 되는데, 이를 N부터 시작해서 1까지 순서대로 R_i와 L_i를 계산하면서 삽입해주면 된다.

5. BOJ 1311 : 할 일 정하기1 - G1
Bit DP 문제였다.

현재 i번째 사람까지 어떤 일들을 맡았을 때 최소 비용을 저장하면 된다. 이는, i-1번째 사람까지 어떤 일들을 맡고 i번째 사람이 아직 안 고른 일들 중 하나 고르는 걸로 계산하면 된다.

 

그래서 DP식은 대강 dp[j|curr][i] = min(dp[j|curr][i], dp[j][i-1] + cost[k][i]) // which = (1 << k) 이런식으로 세울 수 있다.

별해로 MCMF로도 풀린다고 한다.

6. BOJ 9461 : 파도반 수열 - S3
DP 문제였다.
예전에 점화식을 본 기억이 있어 쉽게 풀었다.

 7~13. [GEC-Cup 2024 Open Contest] - (Solved : 7/10)

 

7. BOJ 31668 : 특별한 가지 - B4

Arithmetic 문제.

파묻튀밥의 줄의 개수는 M / N, 각 파묻튀밥을 K 그램의 가지로 바꾸면 되므로 걍  K * M / N을 출력하면 된다.

뭔가 요구하는 바에 비해서 지문에서 '파묻튀', '파묻튀밥' 같이 생소한 용어들을 사용해서 그런지 좀 읽기 어렵게 느껴졌다.

 

8. BOJ 31669 : 특별한 학교 탈출 - B3

Implementation + Bruteforcing 문제.

아무도 순찰하지 않을 때 탈출하면 되므로 세로 줄이 모두 X일 때를 찾아보면 된다.

그리 어렵지 않은 문제.

 

9. BOJ 31670 : 특별한 마법 공격 - S2

DP 문제.

 

dp[0][i]를 i번째 칸에 빔을 쏘지 않았을 때 i번째 칸까지 전부 커버하는 최소비용, dp[1][i]를 i번째 칸에 빔을 쏘았을 때 i번째 칸까지 전부 커버하는 최소비용 이렇게 정의를 하자. 그러면 점화식을 아래와 같이 세울 수 있다.

 

• dp[0][i] = dp[1][i-1] (i-1번째 칸은 항상 커버해야 되므로...)
• dp[1][i] = cost[i] + min(dp[1][i-1], dp[0][i-1]) // i-1번째 칸은 커버하거나 말거나 상관없다.

그래서 나중에 min(dp[0][N], d[1][N])을 출력해보면 된다.

가벼운 점화식 DP 문제로 재밌게 풀었다.

 

10. BOJ 31671 : 특별한 오름 등반 - G5

나는 BFS로 풀었다.

 

처음에는 어떻게 풀지 막막해서 다른 문제들을 풀다가, 그냥 BFS로도 풀릴 수 있다는 생각이 들어 BFS로 풀어보았다.

(0 , 0)과 (2N , 0) 을 기준으로 BFS를 돌렸을 때 둘 다 도달할 수 있는 칸은 실제로 준석이가 등반할 때 도달할 수 있는 칸이 된다. 그래서 BFS를 두 번 돌려서 두 번 탐색된 좌표들을 찾고 이 중에서 제일 높은 y값을 출력하면 된다. (없으면 -1 출력)

 

갑자기 BFS로도 풀 수 있다는 생각이 들었을 때 왜 이걸 빠르게 생각하지 못했나 현타왔었다. 이러면 안 되는데... 그나저나 별개로 타 BFS 문제들이랑 다르게 바로 떠오르는게 쉽지 않았던 문제였던 것 같기도 하다. (실제로 DP 풀이도 많이 나오고는 있다.)

 

11. BOJ 31672 : 특별한 케이크 (easy) - S3

Implementation + Simulation 문제.

말 그대로 모순이 되는 케이스들을 전부 찾아서 이를 시뮬레이션을 굴려보면 된다.

구현 시뮬은 언제나 풀기 귀찮다.

 

12. BOJ 31673 : 특별한 학생회장 교체 - S3

나는 Greedy + Sorting + Parametric Search로 풀었다.

 

학생회 예산을 mid로 잡았을 때, 반대표 개수가 높은 순서대로 남은 예산들 중 mid 만큼 계속 빼서 주었을 때

탄핵이 된다면 l = mid, 아니라면 r = mid로 잡아 최솟값을 찾으면 되었다.

 

그런데 실제 태그는 그냥 Greedy + Sorting이라고 하는데, 생각해보니 정렬해서 그냥 과반수가 되는 학생 단체 개수의 최솟값을 찾고(이를 K라고 하자.) M / (K+1)를 출력하면 되긴 할 것 같다.

 

13. BOJ 31674 : 특별한 기술력 - S2

나는 Ad hoc + Greedy + Sorting + Divide and Conquer(거듭제곱)으로 풀었다.

 

관찰을 해보니, 오름차순으로 정렬한 결과가 a1, a2, a3, ... an이라 하면 a1 + a2 * 2 + a3 * 4 + a4 * 8 + ... + an * (2^{n-1}) 가 최대가 됨을 알 수 있었다.

 

그래서 2^n을 Divide and Conquer로 풀었는데, 이걸 그냥 변수로 하나 두어 매번 2를 곱하고 나머지를 다시 계산하는 방법으로 2^n을 좀 더 효율적으로 구할 수 있었다.

 

이번 주 일지는 여기서 끝.