마지막 목표로 삼았던 다이아 2티어를 드디어 달성했다. 다이아 3에서 약 9개월 정도 걸렸다.
원래 이번 여름방학에는 스프링을 제대로 공부해 볼 계획이었는데, 요즘 들어 알고리즘 대회나 기업 코테를 볼 일이 많았어서 연습한다는 명목으로 백준만 붙잡고 있었던 것 같다. (사실 다이아 문제들을 대회 중에 볼 실력은 아직 아니라서 연습이 됐는지는 잘 모르겠다.)
플래티넘 문제들은 레이팅을 거의 안 줘서 다이아 문제 위주로 고르다 보니, 아직 공부하지 않은 다이아급 알고리즘 기본 문제들이 너무 많았다. 하지만 지금 해봐야 당장 대회에서 응용하기도 힘들 것 같아서, 오히려 잘 알려진 알고리즘들만 사용하는 다이아 문제들을 골라서 풀었다. (쫄아서 그런 거 아님. 아무튼 아님.) 덕분에 구현력도 좋아지고, 기존에 흐릿하게 기억하고 있던 알고리즘들을 리마인드하면서 문제를 접할 때 생각의 폭이 넓어지는 느낌이 들었다.
+) 지금까지 푼 다이아 문제들 중에서, 골드 이하급의 알고리즘만 사용해도 풀리는 것이 보장되는 재밌는 문제들을 골라봤습니다. 풀이를 다 쓰기엔 너무 길기도 하고 스포일러가 될 수 있으니, 더보기에 핵심 관찰이나 힌트 정도만 간략하게 적어 두겠습니다. 여러분도 힌트를 열어보기 전에 한번 도전해보세요!
1. 감성 테트리스 (백준 16856, D4)
승급전으로 풀었던 마지막 문제입니다. 서브태스크 2를 해결해야 3을 풀 수 있기 때문에, 순서대로 생각해보는 것을 추천드립니다.
이 문제는 희소 배열(sparse table)의 사전 지식을 요구합니다.
먼저 서브태스크 2부터 풀어봅시다.
지금 떨어지는 블록을 a라고 하고, a가 떨어지면서 맞닿는 블록 두 개를 b, c라고 합시다. (이때 트리처럼 b, c를 a의 자식으로, b, c의 자식들과 b, c를 포함하여 a의 자손으로 정의하겠습니다.)
블록 b, c가 각각 누르고 있는 블록들의 개수를 알고 있다면, 블록 a가 누르는 블록의 개수는 2 + (b의 자손 수) + (c의 자손 수) - (b, c가 동시에 누르는 블록 수)입니다. (2 = b, c)
(b, c가 동시에 누르는 블록 수)를 알기 위해서는 b, c가 공통으로 가지는 자손 중에서 가장 높은 블록 d를 찾아야 하고, (d의 자손 수) + 1이 (b, c가 동시에 누르는 블록 수)가 됩니다. (1 = d)
이때 b 입장에서 d가될 수 있는 후보는 자신의 오른쪽 자손(초록색 부분)에 있고, c 입장에서 d가될 수 있는 후보는 자신의 왼쪽 자손(파란색 부분)에 있게 됩니다. (자식이 하나밖에 없으면 오른쪽/왼쪽은 무시합니다.)
다시 말해서, 위 그림에서 회색 부분은 볼 필요가 없게 되고, 노란색 부분에서 가장 높은 블록이 블록 d가 되는 것입니다.
이를 희소 배열을 이용하여 적절히 관리하면 서브태스크 2번을 풀 수 있습니다.
이제 서브태스크 3을 풀어봅시다.
'ㅣ'자 블록은 높이가 4이기 때문에, 희소 배열로 자식,자손들을 관리하기 어려워질 수 있습니다.
그래서 'ㅡ'자 블록이 높이가 1이고 폭이 4인 블록이라면, 'ㅣ'자 블록을 높이가 1이고 폭이 1인 블록 4개로 바꿔서 문제를 푸시면 됩니다. 블록의 높은 부분이 낮은 부분들을 자손으로 갖게 되는데, 이때 블록 개수를 4개로 세지 않도록 적절히 구현해주시면 서브태스크 3번까지 풀 수 있습니다.
2. 은퇴한 자들의 게임 (백준 22883, D2)
여태 풀었던 다이아 문제 중 가장 높은 티어의 문제입니다. ㄷㄷ
1년 전에 오기로 며칠을 고민하다 포기했던 문제인데, 최근에 선배님께 힌트를 받아 겨우 풀었던 문제입니다.
내가 말을 움직인 것 때문에 손해를 보게 된다면, 그 말은 움직여서는 안 되는 말입니다.
이 때 손해를 본다는 것은, 같은 게임판에서 상대방과 지그재그로 경쟁했을 때, 내가 먼저 벽에 막혀 움직일 수 없게 된다면 상대방에게 이득이므로 나는 손해를 본 것입니다.
따라서 손해를 보지 않기 위해 나는 어떤 게임판에서 초기에 딱 k번만 움직이고 그만 움직여야 하는데, 좋은 울타리 배치에서는 이 k 값을 이분 탐색으로 찾을 수 있습니다.
3. 돌 옮기기 (백준 28436, D5)
최근에 열린 solved.ac 아레나 #1에 등장했던 문제입니다. 대회 중에 문제를 읽지도 못했는데, 끝나고 푸는 데 한 시간 정도 걸려서 아쉬웠던 문제입니다. 위의 D2 문제를 푼 지 얼마 안됐어서 금방 풀이가 떠올랐던 것 같습니다.
2번 문제와 마찬가지로 내가 움직이는 돌 때문에 상대방이 이득을 볼 수 있다면, 그 돌은 움직여서는 안 되는 돌입니다.
그런데 앞에서부터 탐색하면, 내 뒤에 상대방 돌이 몇 개나 있는지 알 수 없으므로 이득 여부를 알 수 없습니다.
하지만 뒤에서부터 탐색하면, 내 뒤에 돌이 몇 개 있는지 확실하게 알 수 있으므로 돌을 움직일지 말지 그리디하게 결정할 수 있습니다.
4. 체스 (백준 1232, D4)
실제로 체스를 좋아해서 그런지, 풀이는 빨리 떠올랐는데 의외로 구현이 엄청 오래 걸렸던 문제였습니다.
퀸이 두 개의 킹을 동시에 공격할 수 있다면, 다음 턴에 게임은 끝납니다.
킹이 8방향으로 최대 한 칸 밖에 움직일 수 없어서, 퀸은 아래 그림처럼 두 킹과 직각삼각형을 이루는 위치로 이동하려고 노력하면 됩니다.
이 작업이 최대 3턴 안에 이루어진다는 것을 어렵지 않게 증명할 수 있고, 따라서 답은 4를 초과할 수 없습니다.
이제 양 팀이 각각 두 번 움직이는 모든 상태에 대해 직접 시뮬레이션해보고, 그래도 퀸이 저런 위치에 갈 수 없다면 퀸의 다음 움직임은 이미 확정되어 있습니다. 따라서 시뮬레이션을 끝내고 4를 출력하면 됩니다.
5. 라면 사기 (Small), (Large) (백준 18185, D5 / 18186, D4)
다이아 문제 중에 가장 많이 풀렸고, 가장 유명한 문제입니다.
현재 i번 공장에 있다고 가정했을 때, (i+1)번 공장의 라면은 무조건 묶어서 구매하는 게 이득입니다.
하지만 (i+2)번 공장의 라면은 뒤의 구매를 방해할 수도 있으므로 신중히 결정해야 합니다.
그런데 i번 위치에서 (i+2)번 공장의 라면을 좀 덜 구매하더라도, (i+1)번 위치에서 2번 구매 방법으로 커버할 수 있다면, 어차피 (i+2)번 공장의 라면을 구매하는 비용은 C원으로 똑같습니다.
따라서 (i+1)번 공장에서 커버가 불가능한 만큼만 i번 공장에서 3번 구매 방법으로 구매하고, 나머지는 (i+1)번 공장에 구매를 미루면 됩니다.
6. Eight Sins (백준 18484, D5)
문제가 영어라 간단히 요약해 드리자면,
[1~k]의 값을 가지는 오름차순으로 정렬된 배열 $a$에 대해, $i=1$부터 시작해서 질문을 던집니다.
질문한 x값과 실제 $a_{i}$값의 대소관계를 알려주고, 만약 같다면 다음 인덱스로 넘어갑니다.
$1<=n<=100$의 길이를 갖는 배열 $a$의 모든 값을 2600번의 질문 안에 모두 찾아야 합니다.
$2^{29}<10^{9}<2^{30}$ 이므로, 단순히 이분 탐색을 돌린다면 약 3천 번의 질문이 필요합니다.
우리는 이전 값보다 크면서 k보다 작은 모든 값에 대해 이분 탐색을 해야 하는데, 배열 a의 값이 계속 작게만 증가한다면 우리는 질문을 3천 번 정도 할 수밖에 없습니다.
만약 배열 a의 값이 계속 유의미하게 k에 가까워지고 있었다면, 별다른 구현 없이도 2600번의 질문 안에 값을 모두 찾았을 것입니다.
따라서 이분 탐색을 시작하기 전에, 적당히 작은 test 값을 설정해서 미리 물어봅시다.
- 만약 a가 작게 증가해서 test 값보다 작은 구간에 있다고 대답했다면, 우리는 작은 구간만 살펴보면 되므로 이득입니다.
- 만약 a가 test 값보다 큰 구간에 있다고 대답했다면, 배열 a의 값이 유의미하게 k에 가까워지고 있다는 뜻이므로 앞으로의 질문 횟수가 점차 줄어들 것입니다.
7. 정육면체를 사랑하는 사람 (백준 14708, D5)
이 풀이 시리즈를 쓰게 된 가장 큰 이유가 된 문제입니다.
- 박스의 높이를 h로 고정했다고 가정하면, 박스의 옆면을 이루는 겉넓이는 박스의 가로,세로 변의 길이에 의해 결정됩니다.
- 박스의 가로/세로 길이를 각각 a, b라고 했을 때, 가로 길이를 $\pm k$, 세로 길이를 $\mp k$ 한다고 해서 옆면의 겉넓이의 합은 바뀌지 않습니다.
- $(x-a)*(x+a)<=x^{2}$이기 때문에, 박스의 바닥이 정사각형일 때 가장 많은 정육면체를 담을 수 있습니다.
- 만약 바닥을 $x^{2}$ 에서 $(x-a)*(x+a)$ 모양으로 만든다면, 겉넓이는 $2*a^{2}$만큼 감소하고(바닥, 윗면) 부피는 $h*a^{2}$만큼 감소합니다.
- $10^{18}$개의 정육면체를 모두 담기 위해서 $10^{6}$ 길이의 정육면체 모양의 박스가 필요하고, 이때 겉넓이는 $6*10^{12}$입니다. 이것보다 겉넓이가 큰 답은 존재하지 않으므로, 고정할 박스의 높이 h는 특정 값 이상으로 커질 필요가 없습니다.
위의 관찰들을 잘 조합하면 문제를 푸실 수 있습니다.
8. 경비병 세우기 게임 (백준 18939, D4)
다이아 문제 중 가장 간단하면서도 허무했던 문제입니다. 사실, 문제가 출제자분이 의도한 풀이와 다르게 풀려버려서 아쉬워하고 계신 것 같습니다...
이 문제는 힌트의 스포일러가 너무 강력해서, 스스로 풀어보고 싶으신 분은 힌트를 보지 않는 것을 권장드립니다.
또한 제 풀이도 출제자분이 의도한 풀이가 아니므로, 자세한 풀이가 궁금하신 분은 https://upload.acmicpc.net/c87b5b8b-b9cf-49c5-bf20-7b0e28591c31/ 를 참고해주시기 바랍니다.
격자판을 반으로 잘라 생각하면, 상대가 둔 곳을 거울처럼 똑같이 따라 두면 됩니다.
'PS > 백준' 카테고리의 다른 글
| [백준] 새싹10단계 뱃지 획득! 1024일간의 여정 (3) | 2024.05.08 |
|---|---|
| [백준] 겨울방학 동안 1일 1플래티넘 문제 풀기 도전기 (7) | 2024.03.18 |