제3회 청소년 IT경시대회 고등부 (알고리즘 부문) 풀이

대회는 아마 작년(2024) 9월?

왜 지금 쓰냐면 까먹고 있었는데 어제 4회 KITPA가 있었다. 이번엔 게임 이벤트랑 겹치고 3회 때 대상을 땄기 때문에 신청 안했지만..

암튼 까먹고 있다가 오늘 보니까 KITPA 2회 조회수가 올라가있어서 기억났다. 이 글도 좀 일찍 쓸걸 그랬다.

5회 때는 그 전에 4회 풀이를 올릴 수 있게 해야겠다.

근데 솔직히 너무 오래되서 기억이 잘 안난다. 일단 기억나는 대로 서술

난이도는 2회보다 쉽다.

 

1번 - 재미있는 파이프 퍼즐 (링크)

 

solved.ac 티어

Gold V (20250316 기준)

 

풀이

(1,2)에서 시작하는 경우와 (2,1)에서 시작하는 경우를 따지자. 'I'는 무조건 전진해야하고 'L'은 무조건 아래로 가야 하며 아래도 'L'이어야 한다. 항상 전진만 하기 때문에 naive하게 따져주면 된다.

 

 

2번 - 집합 연산 (링크)

 

solved.ac 티어

Platinum V (20250316 기준)

 

풀이

연산을 여러 번 진행할 때의 양상을 관찰하자. 이번 연산이 추가라면 1칸 앞으로 가고 제거라면 1칸 뒤로 간다. 좀 더 구체적으로 보면, 추가할 때는 이미 있는 원소에 접근할 때까지 앞으로 갔다가, 접근하게 되면 제거로 바뀐다. 제거할 때는 없는 원소에 접근할 때까지 뒤로 갔다가, 접근하게 되면 추가로 바뀐다.

이런 식으로 연산의 형태가 바뀌는 횟수는 O(N)번이다. 처음에 주어진 원소가 N개이기 때문이다. 따라서 이렇게 형태가 바뀌기 전까지의 연산을 묶어서 빠르게 처리해주면 되고, prefix sum + set 등으로 잘 관리하면서 각 쿼리 횟수에 도달할 때마다 출력해주면 된다.

 

 

3번 - 스파이 (링크)

 

solved.ac 티어

Platinum III (20250316 기준)

 

풀이

기본 베이스는 보안 등급이 큰 스파이부터 추가하면서, 그 스파이를 거치면서 새로 추가되는 쌍을 세는 것이다. 이건 disjoint한 구간을 관리하는 set과 union-find로 할 수 있다. 하지만 이렇게 하면 직접적으로 정보를 공유할 수 있는 쌍 일부를 세지 못한다. (정확히는 거꾸로 가는 경우) 이건 각 스파이를 보면서, 자기보다 빨리 출근한 스파이 중 자기와 시간이 겹치는 스파이를 관리하면서 세그먼트 트리로 구해줄 수 있다.

 

 

4번 - 하노이의 큐 (링크)

 

solved.ac 티어

Platinum V (20250316 기준)

 

풀이

아래 풀이는 좋은 풀이는 아니다. 코드도 길고 기여를 보면 더 좋은 풀이가 있는 것 같다.

motivation은 잘 모르겠고 풀이는 기억 안나서 노트에 적혀 있는 풀이를 그대로 적겠다.

N = 2^k일 때,

0. 처음에 그룹은 [1,N] 하나이다.

1. [L,R] 그룹을 [L,mid], [mid+1,R]로 쪼갠다.

2, [L,mid]는 나머지 큐 2개 중 front의 그룹이 작은 쪽으로 옮기고, [mid+1,R]은 남은 쪽으로 옮긴다.

3. 이걸 [1,2^(k-단계)] 크기 단위로(ex: [1,2] / [3,4] / ... ) 끝까지 반복한다.

4. 이후 merge sort 하듯이 합친다.

 

이 풀이는 N이 작을 때 32N을 오버할 수 있다. 그래서 N이 작을 때는 L = N^2에 이용되는 naive한 풀이를 쓰면 된다.

 

 

다 쓰고 보니까 좀 산만한데 나중에 다듬어야겠다.