개인적으로 출제한 문제

교내 동아리 입부시험을 위해 문제 출제를 하게 되어, PS문제를 2개정도 만들게 되었습니다.

개인적으로 묻히기에는 꽤 좋은 문제라고 생각해 여기에 후기를 올립니다.

 

문제에 앞서 ...

저희 동아리는 PS동아리가 아닌 관계로 정보 문제를 직접적으로 낼 순 없어서 변형을 좀 가했습니다 ㅋㅋ;;

문제 스토리?등도 있지만 설명하면 너무 길어지는 관계로 간단한 요약 설명합니다.

 

문제 1. 구울

$4N$개의 수가 원형으로 배치되어 있습니다. 각 수는 $-1, 0, +1$중 하나이며, $+1$이 정확히 $3N$개 있습니다. 최종 목표는 모든 $+1$의 위치를 찾아내야 합니다. 이를 위해 $3N-1$번의 쿼리를 이용할 수 있습니다. 하나의 쿼리는, 원 위에서 인접한 수들을 골라 그 합을 반환받을 수 있습니다.

 

풀이

먼저 $3N$ 풀이를 설명합니다. $[1, 2], [3, 4] ... $ 이렇게 2개씩 묶어서 질문하면, 총 $2N$개의 쌍 중에서 적어도 $N$개 쌍의 반환값이 $+2$이어야 함을 증명할 수 있습니다. 나머지 $N$개 쌍마다 한번씩 물어봄으로써 해결할 수 있습니다.

 

$3N-1$ 풀이는 $2N$개의 쌍 중에서 한 쌍을 제외하고 나머지를 물어봅니다. 이후는 그 쌍을 빼고 나머지를 동일하게 처리하면, 그 쌍에 들어있는 $+1$의 수를 알 수 있습니다. 최후 한번의 질문으로 어느쪽이 $+1$인지 알 수 있습니다. 기존 $3N$풀이에서 처음 한번의 질문을 하지 않으므로 총 $3N-1$번에 가능합니다.

 

 

문제 2. 참새

원래 내려고 했던 문제는 다음과 같습니다.

 

전깃줄 위에 $N$마리의 참새가 일렬로 있습니다. 각 참새는 오른쪽 혹은 왼쪽을 바라보는데, 특정한 규칙에 따라 "짹짹" 소리를 냅니다. 각 참새마다 자신과 마주보는 참새의 수 만큼 짹짹 소리를 냅니다. 좀 더 엄밀하게는, $i$번 참새가 오른쪽을 바라보고 있다면, 자신보다 오른쪽에 있고 왼쪽을 바라보는 참새의 수 만큼 짹짹 소리를 냅니다. 당신의 목표는 반대로 전체 참새의 수와, 각 참새가 짹짹거린 횟수를 받아 기존 참새의 방향을 복원하거나, 가능한 상태가 존재하지 않음을 판단해야 합니다. 가능한 상태가 여러개라면 어떤 상태는 가능합니다. (스페셜 저지)

 

입력

참새의 수 $N (1\le N\le 10^6)$과 길이 $N$의 수열 $A_i (1 \le A_i \le N)$ 이 주어진다.

 

출력

가능하다면 길이 $N$의 $0$과 $1$로 이루어진 수열을, 불가능하다면 $-1$을 출력한다.

$1$은 오른쪽, $0$은 왼쪽을 뜻한다.

 

이를 그대로 입부에 내면 아무도 못 풀 것이 분명하니, 적어도 프로그래밍이 아닌 수학 문제로 변형했습니다.

(문제를 푸는 알고리즘이 그대로 나와 있으므로 스포주의)

위를 풀기 위해 다음과 같은 알고리즘을 만들었다. 이 알고리즘의 정당성을 증명하면 된다.

임시로 다음과 같은 수열 $B_i$를 만든다.

$B_i == 1$이면 오른쪽을 바라보고 있는 것을 뜻하고, $B_i == 0$이면 왼쪽을 바라봄을 뜻한다.

 

1. $B_1 := 1$을 한다.

2. $i = 2 ... N$을 순회하며, $A_i == A_{i-1}$ 이라면 $B_i := B_{i-1}$, 아니라면 $B_i := (B_{i+1} + 1)%2$ 를 한다.

3. 만약 현재 수열 $B$의 짹짹거림 수가 $A$와 일치한다면, 찾은 것이므로 종료한다.

4. $i = N ... 1$을 순회하며 $B_i$를 반전시키면서 짹짹거림수가 $A$와 일치하는지 확인을 반복한다.

5. 전부 반전시켰는데 단 한번도 일치한 적이 없다면 $-1$을 출력한다.

 

즉, 인접한 두 새를 봤을 때 서로 짹짹거린 수가 다르면 다르게 배치하고, 같다면 같은 방향으로 배치합니다.

그 후, 맨 뒤부터 하나씩 뒤집으면서 조건을 만족하는지 판단합니다.

 

전체 풀이입니다.

먼저, 알고리즘은 위에 있는걸 누적합으로 적절히 처리하면 $O(N)$에 가능합니다.

 

정당성의 증명은 다음과 같습니다.

 

$A_i != A_{i+1}$ 라면, $B_i != B_{i+1}$ 이어야 합니다.

그러면

$A_i == A_{i+1}$이면 $B_i == B_{i+1}$ 여야 할까요? 이는 거짓입니다.

하지만 "거의 참"임을 알 수 있습니다. 정확히는, 저 명제가 거짓이 되는 지점이 최대 한 지점 존재합니다.

이를 "그 쌍"이라 칭합시다.

그렇다면, 위의 알고리즘은 모든 $[i, i+1]$ 쌍에 대해 "그 쌍"이 되는 경우를 시도해보므로, 정당합니다.

 

최대 한 지점 존재함에 대한 증명은 다음과 같습니다.

$f(i)$를 $1 ~ i$중에서 오른쪽을 바라보는 참새의 수라고 정의하고

$g(i)$를 $i+1 ~ N$중에서 왼쪽을 바라보는 참새의 수라고 정의합시다.

"그 쌍"이 존재하기 위해서는 적어도 $f(i)=g(i)$를 만족해야 합니다. $i$가 $1$증가할 때 $f(i)$가 $1$ 증가하거나, $g(i)$가 $1$ 감소하게 됩니다. 그러므로 둘이 만나는 점이 최대 $1$개 존재할 수 있습니다. 증가함수와 감소함수의 교점이 최대 $1$개임을 생각하면 됩니다.