이번 대회는 처음 1시간 10분 정도 A~C를 풀었고, 마지막에 D번을 구현하던 중에 대회가 끝나 버렸다..
A번
- Div.2 A 에서 보기 드문 단순 구현 문제라는 생각이 든다.
B번
- Div.2 B 치고는 쉬운 문제였으나, 역시나 효율성을 생각해야 하는 문제였다.
C번
- Div.2 C 에 맞는 문제인 거 같았고, 개인적으로 어렵게 푼 거 같다.
D번
- Div2.D 에 맞는 문제인 거 같았다.
- 핵심적인 로직은 빠르게 파악했는데.. 구현을 잘 못해서 망했다.
A. Image
$2 \times 2$ 행렬이 주어지고 모든 색이 같아지게 만들 때 드는 최소 시행 횟수를 구하는 문제이다.
$2 \times 2$ 행렬이므로 칸의 개수는 4개이다.
칸에 있는 색이 모두 다른 경우에는 답이 3이 되고, 모두 같은 경우에는 0이 된다.
따라서, 입력으로 주어진색의 종류가 몇 개인가에 따라서 답이 달라지는 것이다.
실제 대회에선 더럽게 구현했으나, 종류의 개수만 파악하면 되는 문제이니 set 자료구조를 쓰는 게 더 나은 풀이인듯하다.
B. Deadly Laser
$n \times m$ 크기의 2차원 공간에서 $(1, 1)$에서 $(n, m)$으로 가는 최단 경로의 길이를 구하는 문제이다.
단, 레이저에 닿으면 안 되고 갈 수 없는 경우에는 $-1$을 출력해야 한다.
풀이1
이 문제를 푸는 가장 간단한 로직은 2차원 공간에서 레이저 구간을 갈 수 없도록 설정하고 BFS를 돌리는 방법이다.
먼저, 시작점을 $(1,1)$로 설정하여 BFS를 돌린다. 만약, $(n,m)$까지 도달할 수 있으면 그때의 최단 거리를 출력하면 된다. 만약, $(n,m)$까지 도달할 수 없다면 $-1$을 출력하면 된다.
하지만, 이 풀이는 문제에서 요구하는 시간 복잡도를 만족하지 못한다.
테스트 케이스가 최대 $10^4$, 2차원 공간의 크기가 최대 $10^3 \times 10^3$이므로 최악의 경우 $O(10^{10})$ 이 걸림
따라서, 다른 방식의 접근이 필요하다.
풀이2
2차원 공간과 레이저 영역을 표현하면 아래 그림과 같을 것이다.
2차원 공간과 레이저 영역
$n, m$에 따라 검은색 박스의 크기와 형태가 달라질 것이며, $sx, sy, d$에 따라 노란색 레이저 영역의 위치와 크기가 달라질 것이다.
먼저, 최단 거리가 존재하지 않는 경우는 어떤 경우인지를 생각해보자.
최단 거리가 존재하지 않는 다는 것은 $(1,1)$에서 $(n,m)$으로 갈 수 없는 경우이다. 즉, 노란색 레이저 영역이 $(1,1)$에서 $(n,m)$로의 경로를 차단하는 경우와 동치이다. 그러한 경우는 아래와 같이 총 4가지로 나눌 수 있다. 도달이 불가능한 경우 (4가지)
그렇다면, 도달할 수 없는 경우가 아니라면 최단거리는 어떻게 될까?
도달할 수 없는 경우가 아니라면항상 최단 거리는 $n+m-2$가 된다. 이것이 의미하는 바는 위에서 말한 4가지 경우가 아니라면 항상 위와 오른쪽으로만 이동해서 $(n,m)$으로 도달할 수 있다는 것이다. 이는 조금만 생각하면 이해할 수 있을 것이다.
이 풀이는 4가지 경우를 판단할 때 $O(1)$이 걸리며, 테스트 케이스는 최대 $10^4$이므로 시간 복잡도는 최악의 경우에도 $O(10^4)$이다.
C. Min-Max Array Transformation
크기가 $n$이고 정렬된 상태의 배열 $a, b$가 존재하며
이때 $d_1^{max}, d_2^{max}, \dots, d_n^{max}$ 와 $d_1^{min}, d_2^{min}, \dots, d_n^{min}$ 을 구하는 문제이다.
이 문제에서 배열 $a$와 $b$가 매칭이 되는 경우는 적어도 1개 존재한다고 했으므로 정답도 항상 존재하게 된다.
먼저, 매칭이 어떤식으로 되는지를 살펴 보자.
$a_i$가 $b_1$과 매칭이 될 때 $d_i$가 최소가 될 것이며, $b_n$과 매칭이 될 때 $d_i$가 최대가 될 것이다. 그런데 이와 같은 상황이 항상 가능한 것은 아니다. 그러한 이유는 다음과 같은 조건이 있기 때문이다. 1. $a_i$는 $a_i \leq b_j$를 만족하는 $b_j$와 매칭이 될 수 있다. 2. $i \neq k$인 $a_k$가 어떠한 $b_j$와 매칭이 된다면 $a_i$는 $b_j$와 매칭을 할 수 없다.
이제, 우리는 위의 조건 1, 2를 만족하면서 $d_i$의 최댓값과 최솟값을 찾으면 된다.
처음에 문제에서는 항상 답이 존재한다고 했다. 이 말은 즉슨, 적어도 1개의 매칭은 가능하다는 의미이다. 이는 모든 $i$에 대해 $a_i \leq b_i$ 를 항상 만족한다는 의미이다. 이를 만족하지 않으면 $k$개의 원소를 $k$개 보다 작은 원소와 매칭해야 하는 상황이기 때문이다.
배열 $a$, $b$는 항상 정렬되어 있다는 점을 생각해보자. 어떤 $a_k$가 $b_j$와 매칭을 할 수 있다면, $i < k$인 $a_i$또한 $b_j$와 매칭이 될 수 있다. 따라서, $i < k$ 라면 $a_k$에게 먼저 선택권을 주는 것이 맞을 것이다. 이러한 과정을 $i=n$부터 $i=1$까지 거치며 $a_i$가 매칭 가능한 경우를 살펴 보면 $d_i$의 최솟값과 최댓값을 구할 수 있다.
핵심은 $b_{i-1} < a_{i} \leq b_{i}$을 만족하는 어떤 지점 $i$가 있다면 $a_{i \sim n}$과 $b_{i \sim n}$에서 모든 매칭이 이루어져야 한다는 점이다. 따라서, $a_{1 \sim (i-1)}$은 $b_{i \sim n}$와 매칭이 될 수 없다는 것이다.
사실, 이 문제를 배열 $a$의 원소와 $b$의 원소를 1:1로 매칭하는 문제로 해석할 수 있다.
위에서 말한 조건 1을 만족하는 경우에 그러한 $a_i$와 $b_j$를 간선으로 연결시키면 그래프(이분매칭) 형태로 표현이 가능하다.
이해가 안 간다면, 아래와 같이 상황을 그래프로 표현해보길 바란다.
상황을 그래프로 표현
위와 같은 경우는 $a_{3 \sim 4}$과 $b_{3 \sim 4}$에서 모든 매칭이 이루어져야 하므로 $a_{1 \sim 2}$은 $b_{3 \sim 4}$와 매칭이 될 수 없다. 즉, $a_{1 \sim 2}$은 조건 1은 만족하지만 조건 2를 만족하지 못하여 $b_3$, $b_4$와 매칭될 수 없다는 것이다.
D. Maximum AND
크기가 $n$인 배열 $a, b$에 대해 $c_1 \ \& \ c_2 \ \& \ \cdots \ \& \ c_n$ 의 최댓값을 구하는 문제이다.
이때, $c_i = a_i \oplus b_i$ 이며 배열의 $b$의 순서는 임의로 바꿀 수 있다.
즉, 배열 $a$와 배열$b$의 원소를 1:1로 매칭시키는 경우와 동치이다.
이러한 문제를 풀 때에는 비트 연산 $\&$와 $\oplus$이 어떠한 의미를 가지는지 생각해보면 도움이 된다.
$c_1 \ \& \ c_2 \ \& \ \cdots \ \& \ c_n$ 결괏값은 숫자이므로 2진수로 표현했을 때 1의 개수가 많으며 상위 비트가 1이 될 수록 값이 커진다.
어떻게 하면 $c_1 \ \& \ c_2 \ \& \ \cdots \ \& \ c_n$의 결괏값 $c_{res}$의 $k$번째 비트를 1로 만들 수 있을까?
편의를 위해서 $N(k)$는 숫자 $N$의 k번째 비트를 의미한다고 하겠다.
$c_{res}(k)$가 1이 되려면 $c_1(k), c_2(k), \cdots, c_n(k)$가 모두 1이어야 한다. $c_i(k)$가 1이 되려면 $a_i(k) \oplus b_i(k) = 1$이 돼야 하며, 이는 $a_i(k)$와 $b_i(k)$의 비트가 다를 때를 의미한다. 즉, $a_1(k), a_2(k), \cdots, a_n(k)$와 $b_1(k), b_2(k), \cdots, b_n(k)$를 비트가 모두 다르게 매칭시키면 된다.
어떠한 경우에 $a_1(k), a_2(k), \cdots, a_n(k)$와 $b_1(k), b_2(k), \cdots, b_n(k)$를 비트가 모두 다르게 매칭시킬 수 있을까?
$a_1(k), a_2(k), \cdots, a_n(k)$와 $b_1(k), b_2(k), \cdots, b_n(k)$는 모두 0또는 1이다. 비트가 모두 다르게 매칭된다는 것은 (0,1) 형태로 매칭이 $n$개가 돼야 한다. 따라서, 0과 1의 개수는 같으며 둘 다 $n$개일 때 $c_{res}(k)$를 1로 만들 수 있는 것이다.
이제 끝났다!
수를 비트로 표현했을 때 1000이 0111보다 크다. 즉, 상위 비트부터 시작해서 $c_{res}(k)$가 1이 될 수 있는지 살펴본다. 만약, $c_{res}(k) = 1$이 될 수 있다면 $c_{res}(k)=1$이 되도록 매칭시킨다.
매칭시킨다는 의미가 좀 어려울 수 있는데, 이해가 안 간다면 직접 테스트 케이스를 그려보기 바란다.
check(idx, i)는 현재 부분 배열에 대해 $c_{res}(i)$이 1이 될 수 있는지를 판별하는 함수이다.
divide(x)는 $c_{res}(x)$를 1로 되도록 매칭시키는 것이다.
나는 매칭되는 과정을 분할 정복을 이용해서 구현했는데, 여기에서 jiangly님 코드를 보면 엄청 간단하게 구현하였다.
느낀점
문제 지문이 영어인 점과 문제를 푸는 속도가 느린 점을 개선하면 레이팅을 많이 올릴 수 있을 것 같다!
최근에 코드포스 문제를 푼 후에 완벽히 이해하는 과정을 거치고 있는데, 정말 도움이 많이 되는 것 같다.
