BOJ 31439 선형대수학: 개념과 방법

난이도: Platinum I (체감상 Diamond V)

태그: #애드혹, #해구성, #많은조건분기

 

좀 무식하게 푼 거 같긴 하지만 오랜만에 어려운 문제 하나 풀었고 원래 풀이와도 약간 다른 것 같아서 생각 과정과 함께 올려봅니다.

 

Statement

 

 

Solution / Thought Process

 

Subtask 1 (N = 17)을 보고 백트래킹을 해야 되겠다 생각했습니다. 구현 과정은 그렇게 어렵진 않습니다. 

N = 17이 되는 것을 확인하였으나, 홀수는 N = 11부터 되고, 짝수는 N - 1일 때 제외하고는 (전체 배열을 보면 안 된다는 것이 자명하게 보입니다.) 안 된다는 점을 파악했습니다. N이 작을 때 (<=17) 는 예외가 많을 것 같아서 백트래킹을 돌리는 걸로 했습니다.

그래서 앞으로 이야기하는 케이스는 모두 N>17를 전제로 합니다.

 

그래서 이가 큰 수에도 적용한다는 가정을 하면서 Subtask 2 (N은 짝수)를 풀었습니다. 최대한 경우의 수를 줄이기 위해 N과 1을 붙여놓고, 짝수/홀수를 이어붙이는 방법을 생각했습니다.

그리고 또 하나의 조건은 이웃한 원소의 차가 2가 되면 안 된다는 점입니다.

그러면 짝수 구간 / 홀수 구간만 선택하면 max - min이 4 이상 짝수이며, 짝수 / 홀수 구간을 동시에 고를 시 max / min이 N / 1임이 보장됩니다.

또한, 나중에 홀수 N으로 할 때 홀/짝 간 interaction에서 max(X)-min(X)의 서로 다른 값을 최소화하기 위해, N 바로 옆에 가장 작은 짝수인 2를 놓았습니다.

이 때, N이 충분히 큰 짝수이고 (>=18면 충분합니다) N - 1이 합성수이면 항상 해구성이 가능합니다.

예를 들어서 N = 16이면

12 8 4 14 10 6 2 16 1 5 9 13 3 7 11 15

가 가능합니다. 볼드체 친 수들은 위치관계가 중요한 이들입니다.

 

Subtask 3 [홀수]

여기가 많조분이 많이 어렵습니다.

Subtask 2하고 N-1하고 1 사이에 N을 넣으면 되지 않나? -> 이건 애초에 N-1이 유효한 순열을 가져야 하기 때문에, N-2이 합성수일 때만 성립합니다.

예를 들어서 N = 17이면

12 8 4 14 10 6 2 16 17 1 5 9 13 3 7 11 15

가 가능합니다. (N = 16에서 추가된 min, max 순서쌍이 (2, 17), (1, 17), (16, 17)밖에 없으므로 성립)

 

그러면 N-2가 소수일 때는 어떨까요?

그래서 처음에는 N 옆에 2를 두는 대신, 4 또는 6을 만나면 어떨까 생각했는데 그러면 언젠간 2를 만나면 값이 N-2 (소수)여서 실패합니다.

그래서 이보다 한 단계 아래인 N-4를 생각해봤는데, N-4이면 제한이 너무 많이 걸릴 것 같아서 없다고 가정하고 N-4가 합성수인 경우부터 살펴봤습니다.

이를 만족하는 예시 N = 19를 살펴보겠습니다.

그러면 우리는 (max, min) 짝이 (18, 1), (19, 2)면 안 되므로 [...18...19...1...2...] 순서대로 배열되어야 합니다.

짝수를 최대한 많이 만들기 위해 2만 끝에 박아두면 될 것 같다는 생각이 들었습니다.

그리고 전에 있는 아이디어를 비슷하게 사용 시, N-1 (18) 바로 옆에는 N (19)하고 4가 들어가야 한다는 점을 파악할 수 있습니다. 그 뒤 짝수, 홀수 그룹은 지난 subtask와 동일하게 묶으면 됩니다. 단, 이 때 추가할 점은 N-2로 끝나야 한다는 점입니다. 그래야 2와 이웃해서 차가 N-4가 되기 때문입니다.

즉, N = 19일 때는 다음과 같은 구성이 가능합니다.

14 10 6 16 12 8 4 18 19 1 15 3 9 5 11 7 13 17 2

이 때 <14 ... 18>을 E1, <19 .... 17>을 O라 하면 이가 성립하는 이유를 보일 수 있습니다:

i) 같은 그룹에만 속할 시: 4 이상 짝수만 나오므로 소수 아님

ii) E1 - O를 지날 시: Max는 N(19)가 확정, Min은 18, 4, 또는 1이 가능하고 이들의 차는 모두 소수가 아니므로 (N-4가 합성수라는 케이스기 때문에) 성립

iii) E1 - O - 2 혹은 O - 2를 지날 시: 가능한 순서쌍이 (2, 17), (1, 17), (1, 19) 3개므로 성립.

-> 항상 소수가 아님

이 때, 홀수로 이루어진, 1로 시작하고 N-2로 끝나며 이웃한 수의 차이가 2가 아닌 수열은 N을 4로 나눈 나머지에 따라 백트래킹 등 없이 구성이 가능합니다.

 

이렇게 해서 제출했더니 아직도 57점이 나왔고, 나중에 검사를 해도 틀린 부분이 없어서 N-4가 소수일 때 구성이 안 된다는 가정이 틀렸다는 생각을 해봤습니다.

그래서 백트래킹을 통해 N = 15를 돌려본 결과 (N-2 = 13, N-1 = 11은 소수), 다음과 같은 패턴이 띄었습니다.

앞에는 2, 1, 5, 4가 보이고 15 옆에는 6이 놓여있습니다. 이 때, N-2, N-4가 소수일 때, N>17이고 N-2, N-4, N-6은 모두 mod 3이 다르기 때문에 N-6이 합성수임이 보장됩니다.

여기서 전에 이용한 비슷한 논리를 적용 시,

[2, 1, 5, 4] + [N-2] + [3] + [나머지 홀수] + [N] + [6] + [나머지 짝수]를 구성하면 될 것이라는 생각을 했습니다.

예를 들어서, N = 21일 때, 

2 1 5 4 19 3 7 11 15 9 13 17 21 6 10 14 18 8 12 16 20

전과 비슷한 논리로 나오는 max - min 값은 항상 소수가 아님을 증명할 수 있습니다.

즉, N이 충분히 크면 모든 홀수가 가능함을 보일 수 있습니다.

 

이렇게

i) N<=17

ii) 짝수

iii) N-2 합성수

iv) N-2 소수, N-4 합성수

v) N-2 소수, N-4 소수 (N-6 합성수)

순서로 나눠서 구현 시 AC를 받을 수 있었습니다.

 

고려해야 할 사항이 굉장히 많긴 했지만, 어떻게 해야 max - min 수를 최소화하면서 구성할 수 있었는지 구하는 것이 흥미로웠습니다 :)