Problem Solving Diary #10

JOI Spring Camp 2015년의 문제 세 개를 골라서 풀었다. 대략적인 풀이와 떠올리는 과정 정도만 간단히 적어보려고 한다.

 

BOJ 17716. Copy and Paste 2

문제를 딱 보면 거꾸로 풀기라는 생각이 들었고, 바로 짜서 풀었다. 사실 거꾸로 푸는 문제를 한 번도 풀어본 적이 없다면 그 아이디어를 스스로 떠올리기는 상당히 힘들다고 생각한다. 하지만 이러한 유형을 많이 풀어 보면 그 특유의 느낌이 오는 것 같다. 문제 형태가 매우 간단하고, 시간 복잡도도 log 같은거 붙지 않고 깔끔하게 나와야 할 때 쓴다는 느낌?

 

유사한 아이디어를 쓰는 문제 몇 개가 있다. 이런 문제 유형 특성상 아이디어 자체가 매우 큰 스포일러라는 점을 조심하자.

 

유사한 아이디어를 쓰는 문제로 KOI 중등부 트리, NYPC 덧셈 프로그램 등이 있다. 후자는 시험장에서 푸는 데 꽤 애를 먹었다. 

 

 

BOJ 17727. Memory (백준에 없음, oj.uz 링크로 대체)

JOISC에서 정말 좋아하는 비트 찍기 유형이다. 기본적으로 생각할 수 있는 건 여는 괄호를 스택처럼 들고 다니는 건데, 이렇게 하면 2^(n/2) 비트가 필요하니 패스. 그 다음으로 생각할 수 있는 건 각 괄호별로 따로따로 보면서 반대편에 짝지어주는 괄호가 있는지 보는 방법이다. 모든 괄호에 대해 짝지어줄 수 있는 괄호가 존재하면 올바른 괄호 문자열이 된다. 뭔가 쿼리 제한이 $O(N^2)$라는 점에서 착안해서 떠올렸던 것 같다.

 

구현의 편의상 여는 괄호에 대해 짝짓는 닫는 괄호가 있는 지만 봐주는 것이 좋을 것 같다. 근데 이걸 하려면 닫는 괄호와 여는 괄호의 수가 같은지를 사전에 체크해 줘야 한다. 아니면 )(()) 같은 방법이 가능하다. 그래서 이걸 먼저 해 줘야 하는데, 이건 현재 위치와 현재까지의 여는 괄호 개수를 가지고 다니면 쉽다.

 

다음으로 여는 괄호에 대해 짝짓는 닫는 괄호를 찾아 주는데, 이건 현재 보는 여는 괄호의 위치 i, 현재 보는 칸의 위치 j, 현재 depth, 상태 네 가지 변수를 가지고 다니면 된다. 각각이 무엇인지는 mechanism을 보면 이해할 수 있다.

 

여는 괄호 i에 대해, 짝이 맞는 괄호(모양은 생각하지 않는다.)를 찾을 때까지 j를 늘린다. depth를 여는 괄호에서 +1, 닫는 괄호에서 -1 하면서, 상태를 0으로 유지한 채로 계속 가는 것이다. 이렇게 하다가 depth가 처음과 일치하는 시점이 나오면 그때가 우리가 찾던 닫는 괄호가 된다.

 

이제 이 닫는 괄호를 찾았으니 상태를 그 모양에 따라 1 또는 2로 바꾸고, 다음 상태에서는 여는 괄호와 모양이 같은지 체크해주면 된다. 이렇게 하면 이용하는 상태 수가 3N^3 정도가 되기 때문에 충분히 돌아간다.

 

BOJ 17728. Walls

일단 Subtask 1은 그냥 주는 거니까 빠르게 긁고 시작했다. Subtask 2를 봤는데 조금 특이하게 생겼다. 보통 이렇게 특이하게 생긴 경우는 서브태스크 줄 게 없어서 억지로 준 거거나, 결정적인 힌트를 내포하는 경우가 있다. 45점이나 주는 거 보면 억지로 준 건 아닌 것 같고, 힌트가 있겠다 싶어서 먼저 풀어보기로 했다.

 

조금 생각하다 보면 중요한 건 구간의 크기라는 것을 알 수 있다. 구간의 크기가 같으면 그 시작점에 상관없이 어느 순간부터 같은 이동을 반복하게 될 것이라는 걸 짐작할 수 있다. 실제로도 그렇다. 거기서 한 발짝 더 나아가서, 구간의 크기가 0부터 시작해 점점 커지면 어떻게 될지를 생각해 봐야 한다. 이때, 좌우로 꺾는 횟수가 점점 줄어든다는 것을 눈치챌 수 있다.

 

중요한 것은, 없던 꺾는 이동이 생길 일은 절대 없다는 것이다. 그저 원래 있던 것이 줄어들 뿐이다. 이런 형태를 보니 set을 사용해서 왔다갔다 이동하는 거리를 관리하고 싶은 욕구가 들었다. 더 이상 쓸모없어질 때 set에서 제거하면 그만이기 때문이다. 그리고 이걸 효율적으로 하려면 거리가 작은 이동 구간부터 뽑아내는 자료구조가 있으면 좋을 것 같은데, 그것도 set으로 하면 되겠다. 이렇게 하면 (위치, 입력 index)를 담은 set과 (시작 위치, 끝 위치, 거리 차이)를 담은 set 이렇게 두 개의 set을 관리하면서 문제를 풀 수 있을 것이다. 사실 시작 위치 때문에 이렇게 단순하게는 안 되고, 조금 까다로워지긴 하는데, 여기는 minor detail이니 패스. 처음에 어떤 방향으로 이동해야 하는지를 기준으로 두 가지로 나눠서 풀면 구현이 편하다.