[백준] 2023 인하대학교 프로그래밍 경진대회(IUPC) Open Contest 후기

https://www.acmicpc.net/contest/view/987

2023 인하대학교 프로그래밍 경진대회(IUPC) Open Contest

 

 

 

 

[문제 풀이]
A번. 모비스
https://www.acmicpc.net/problem/28074

28074번: 모비스

단순 구현. M, O, B, I, S가 들어있는지만 확인해주자.

 



B번. 스파이

https://www.acmicpc.net/problem/28075

28075번: 스파이

하루에 할 수 있는 일이 총 6가지 종류이므로, 모든 경우의 수는 $6^N$이다. 이때 $N$이 8이하의 수이므로 완전탐색으로 문제를 해결할 수 있다. 같은 장소에서 임무를 연속으로 할 경우 절반의 진척도를 얻음에 유의하며 구현해야 한다.

C번. 멀티탭 충분하다

https://www.acmicpc.net/problem/28076

28076번: 멀티탭 충분하다

( 준비 중 )

E번. 중력 큐

https://www.acmicpc.net/problem/28078

28078번: 중력 큐

다른 것보다도 구현이 난관인 문제. 차례대로 케이스를 나누어보면..

큐의 앞이 어디를 보고 있느냐를 저장하는 변수 type을 만든다. 큐의 앞이 오른쪽, 아래쪽, 왼쪽, 위쪽을 바라보고 있을 때의 상황에 대하여 각각의 type 값을 0, 1, 2, 3이라고 지정하자.

우선 삽입. 가림막은 그냥 집어넣으면 되므로 신경써야 할 것은 공이다. 공이 떨어질 수 있는 경우는 type이 1이거나 3인 경우이다.

• type이 1인 경우 : 아래쪽에 가림막이 있어야 공을 삽입할 수 있다. 만약 없다면, 애초에 큐는 텅 비어있었을 것이기 때문에, 중력큐가 비어있으면 공은 그대로 떨어지고 그렇지 않다면 공을 삽입할 수 있다.
• type이 3인 경우 : 공을 삽입하자마자 떨어질 수 밖에 없다.

다음으로 회전. 역시 회전한 결과의 type이 1이거나 3인 경우를 신경쓰자. 두 경우 모두 아래쪽부터 위쪽으로 훑으면서 가림막이 나올 때까지(또는 중력큐가 빌 때까지) 공을 빼내면 된다. 물론 중력큐의 앞뒤 방향에 주의하여야 한다.

마지막으로 pop. type이 1이거나 3인 상태에서 가림막을 빼낸 경우만 신경쓰면 된다. 가림막이 빠졌을 때의 판정은 회전의 경우와 비슷하게 처리하면 된다.

차분히 생각해보면 신경써야 할 케이스는 몇 가지 안 나온다. 단지 조금 귀찮을 뿐..

H번. 직사각형 피자

https://www.acmicpc.net/problem/28081

28081번: 직사각형 피자

가로 방향, 세로 방향의 커팅에 대하여 나누어진 피자의 $x$좌표 길이와 $y$좌표 길이를 따로 구분하여 놓자. 예제의 $x$좌표 길이 묶음은 {1, 4, 2}, $y$좌표 길이 묶음은 {2, 3}이 된다.

커팅 개수 $N$, $M$이 100 000 이하이므로 단순하게 풀면 $O(NM)$이라 시간 초과가 난다. 모든 쌍을 보지 않고, 피자 크기가 $K$ 이하가 될 수 있는 쌍만 탐색해보도록 한다. $x$ 좌표든 $y$ 좌표든 어느 한 좌표 길이 묶음을 기준으로, 다른 좌표 길이 묶음에서 이분탐색을 돌린다.

구체적으로, $x$좌표 길이 묶음에서의 어떤 값 $a$에 대하여, $y$좌표 길이 묶음에서의 $k/a$ 초과인 값의 인덱스를 $i$라고 하자. 조건을 만족하는 피자 조각 개수는 $i$개이다. ( $0 \leq i$ )

J번. 마왕의 성

https://www.acmicpc.net/problem/28083

28083번: 마왕의 성

스코어보드 따라가다 보니 플레 문제를 풀게 되었다. 난이도 공개됐을 때 기분은 좋았는데, 나머지 골드를 못 풀어서 한편으로는 또 찝찝하기도 하고..

모든 칸에 대하여 걷을 수 있는 최대의 세금을 구해야 하므로, 단순한 방법으로는 $O(N^2M^2)$이라 시간초과가 난다. 각 칸의 답을 구해나가는 순서를 강제하면 시간복잡도를 줄일 수 있다. 땅의 높이가 낮은 칸부터 높은 칸 순으로 탐색해나가면, 그 칸이 지금까지의 탐색 칸들 중 가장 높은 칸이므로 답을 쉽게 구할 수 있다. 상하좌우로 현재 탐색하는 칸보다 낮은 칸이 있다면 그 칸과 현재 칸을 묶어주자. 이렇게 묶인 칸들은 항상 다음 탐색하는 칸의 높이보다 낮거나 같으므로 마왕 성의 위치 조건이 항상 성립할 수 있게 된다. 무언가를 하나의 그룹으로 묶는 데는 주로 Union-Find(유니온-파인드)를 사용하므로 이 문제에서도 이를 사용하면 된다. 
 
아이디어가 크게 어렵다는 생각은 들지 않는데, 그에 따라오는 구현이 조금 힘들다. 2차원 Union-Find(유니온-파인드)를 처음 구현해봤는데, 손도 꼬이고 뇌도 꼬이는 기분이었다. 특히 땅뿐만 아니라 세금까지도 같이 묶어줘야 하기 때문에..
 
 
 
 

[업솔빙]

(추후 추가 예정)