어제 낮에 쳤던 버추얼 라운드. 어려웠다
A. In-game Chat
문자열의 끝에서부터 연속된 )의 개수가 전체 길이의 절반을 초과하는지 찾는 문제.
반복문을 뒤에서부터 돌면서 찾으면 된다.
B. Fair Numbers
정수의 각 자리의 수들로 모두 나누어지는 정수를 찾아야 한다. 주어진 정수 이상의 수들 중 조건을 만족하는 가장 작은 수를 찾는 문제.
처음에 직접 정수를 만드는 규칙을 찾으려고 해서 많이 헤맸다. 울프람알파에 주어진 테케를 이것저것 넣다 보니까 lcm(1,2,3,4,5,6,7,8,9)=2520라는 사실을 찾아냈다. 이는 어떤 정수가 어떤 수로 이루어져 있든지, 2520 내에서 최소 한번의 약수가 존재한다는 뜻이다. 주어진 정수에서부터 brute-force로 1씩 증가시키면서 조건을 만족하는 가장 작은 수를 찾았다.
C. Peaceful Rooks (업솔빙)
체스판의 크기와 룩 1 이 주어지고 이 룩들이 서로를 공격하는 위치에 정지하지 않으면서 전부 주대각선 2 으로 몇 번만에 이동시킬 수 있는지 알아내는 문제.
전혀 감을 잡지 못했다. 에디토리얼을 보고 나름대로 이해하고 정리해보았다. 직관과 뇌피셜로 범벅이 된 해설이므로... 에디토리얼을 직접 보기 바란다.
먼저 한 개의 룩이 어떻게 움직이는지 생각해보자. 룩은 가로 또는 세로로 무한정 움직일 수 있으므로 원하는 위치로 움직이기 위해 최대 2번 움직인다. 따라서 각 룩에 대해서 0~2번 사이에 모두 주대각선 위로 움직일 수 있다. 초기 위치가 이미 주대각선 위인 경우, 0번 움직인다. 문제에서 최소한으로 이동해야 한다고 했으니, 초기 위치(x_i, y_i)가 (x_i, x_i) 또는 (y_i, y_i)로 1번만에 이동하는 경우가 최적일 것이다. 그런데 이런 방식으로 이동하지 못 하는 경우도 있다. 이 두 위치와 이미 다른 룩의 위치가 일직선에 있는 경우 즉, (x_i, y_j), (y_i, y_j), (x_j, x_i), (x_j, y_i) 에 있는 경우다. 이렇게 다른 룩에 "점유된" 상태를 Disjoint-set으로 표현할 수 있다. 점유된 좌표 (x_i, y_i)를 merge하자. 만약 (x_j, y_j)를 이동하려고 할 때, x_j와 y_j가 같은 집합 내에 있다면 둘 중 최소 하나의 좌표는 이미 "점유"되어 있으므로 2번 이동하여 다른 주대각선 위치로 이동해야 한다. 이러한 방법으로 각 룩에 대하여 0번, 1번, 2번만에 주대각선에 도착하게 만들 수 있다.