[Atcoder] ABC 361

A번 - Insert (1:41, +, AC)

 

길이 $N$짜리 배열 $A$가 주어지고 인덱스 $K$번째에 원소 $B$를 삽입하여 출력하는 문제.

파이썬에서는 insert라는 함수를 사용하면 된다.

B번 - Intersection of Cuboids (32:37, +4, AC)

이 문제 때문에 그냥 이번 ABC가 다 말림.

입력 예제만 보고 4번이나 잘못짜서 그냥 망침.

마지막에는 다 갈아엎고 다시 짰음.

핵심은 $x, y, z$축은 전부 다 따로 봐도 되고, 하나의 구간이 다른 구간이랑 겹치는지의 여부만 판단하면 됨.

하나의 구간이 다른 구간이랑 겹친다면, 구간의 형태는 [max(왼쪽들), min(오른쪽들)]이다.

따라서 이를 활용하여 함수를 구현하고, 그걸 각 축마다 해준다.

백준에 이 문제의 상위호환 문제가 있는데, 아래 링크에 있다.

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

C번 - Make Them Narrow (38:27, +1, AC)

B번을 조지는 바람에 이 문제도 급하게 제출하느라 1틀 했다.

길이 $N$짜리 수열 $A$가 주어지고 그 수열에서 $K$개의 원소를 제거했을 때의 최댓값과 최솟값의 차의 최솟값을 구하는 문제.

$A$를 정렬한 뒤, $K$개의 원소를 제거한 뒤의 수열, 즉, $N - K$의 길이를 투포인터로 옮기며 (max - min)의 최솟값을 다 찾으면 된다.

시간 복잡도는 $\mathcal{O}(N)$

D번 - Go Stone Puzzle (67:54, +, AC)

전형적인 BFS문제. 최단 횟수를 구하는 문제인데, 빈 공간 두 개로 옮기는 것을 하나의 상황으로 봐서 그래프로 모델링하면 BFS로 풀 수 있다. 구현이 조금 귀찮을 뿐.

일단 W와 B의 개수가 같아야 함에 유의하여 BFS를 돌리자.

개수가 같지 않다면 무한 루프에 빠질 수도 있다.

E번 - Tree and Hamilton Path 2 (Not Solved)

(업솔빙 예정)

F번 - x = a^b (Not Solved)

다 풀고 시간이 30분 정도 남았는데 E번은 제목보고 걸렀고 F번이 할만해 보였는데, 딱 봐도 시간초과나는 풀이를 일단 내보자 해서 틀렸다.

(업솔빙 예정) 

G번 - Go Territory (Not Solved)

(업솔빙 예정)