BOJ 1146 : 지그재그 서기

문제 링크 : https://www.acmicpc.net/problem/1146

 

1 ~ N 의 순열 중에서, 인접한 두 수의 대소관계가 번갈아가면서 나타나는 순열의 가짓수를 세는 문제다.

 

우선 관찰을 해보자.

만약 첫 번째 수가 두 번째 수보다 작다면, 수열은 대략 아래와 같은 개형을 가질 것이다.

즉 1 ~ N 까지의 수들 중 서로 다른 두 수 a, b (a < b) 를 선택하여 위 처럼 배치 가능하다.

여기서 중요한 사실은, a 는 이제 이후의 수열에 아무 영향을 안 준다는 것이다.

이제는 b가 처음이라고 봐도 되는 것이다.

 

a, b 를 선택하여 배치했으니, 남은 N-2 개의 수들을 살펴보자.

b 의 다음 수로 가능한 수는 몇 개일까?

b 보다 작아야하므로 1 ~ b-1 인데, 이 중에서 a 는 이미 사용했기에 b - 2 개라는 것을 알 수 있다.

즉 이후의 N-2 개의 수는 첫 수로 b - 2 가지가 가능하다.

DP 를 적용할 수 있는 형태가 나온 것

b 다음 수가 정해졌으니, b 도 a 와 마찬가지로 더 이상 뒤의 n-2 짜리 순열에 영향을 안 준다.

이제 DP 라는 것을 알았으니, 점화식을 정의해보자.

Up[n][a] := 길이 n 짜리 순열 중 첫 수가 a 이며 오르막으로 시작하는 순열의 총 가짓수

Down[n][a] := 길이 n 짜리 순열 중 첫 수가 a 이며 내리막으로 시작하는 순열의 총 가짓수

 

이 글에서는 Up[n][a] 를 구하는 것만 서술한다. Down 은 완전히 대칭적으로 하면 된다.

Up[n][a] 를 구하려면, 우선 a 다음 수인 b 를 찾아주면 된다. b 의 범위는 당연히 a+1 ~ n 이다.

b 를 찾은 후, 위에서 기술한 대로 남은 수는 n-2 개고, 시작 수로 가능한 수는 1 ~ b-2 이다.

 

혹시나 여기서 b-2 개인 것은 알겠는데 왜 1 ~ b-2 인지 이해가 안 갈 수 있다.

앞서 말했듯 첫 수 a, b는 이제 뒤에 영향을 안 주니까, a 와 b 를 뺀 n-2 개의 수를 1~n-2 로 Re-Labeling 해도 된다.

그렇기 때문에 1 ~ b-2 가 길이 n-2 순열의 첫 수로 가능하다.

 

유사 코드는 아래와 같다.

/* Up[n][a] 구하기 */

for(b = a+1; b <= n; b++){  // a 다음 수 b 는 a 보다 크다
	for(i = 1; i <= b-2; i++){  // b 다음 수는 b-2 개가 가능하다. (a 가 빠지므로)
    	Up[n][a] += Up[n-2][i]; // 남은 n-2개 순열이 i로 시작하는 각 경우들을 다 더해준다.
    }
}

각 (n, a) 쌍마다 이중 for 문이 필요하므로 전체 시간복잡도는 O(N⁴) 이다.

Down 도 똑같이 채우면 된다.

 

답은 (Up[n][1] + Up[n][2] + ... + Up[n][n-1]) + (Down[n][2] + Down[n][3] + ... + Down[n][n]) 이다.