[백준 1146번] 지그재그 서기

문제 링크: 1146번 지그재그 서기

https://www.acmicpc.net/problem/1146

 

가장 나이브하게 풀면 어떻게 될까? 어떤 숫자가 몇 번째 줄에 위치한다는 것을 정한 상태에서, 다른 숫자의 사용 여부를 저장해둔 다음 안 쓴 숫자 중 하나를 골라서 다음 줄의 상태를 탐색해나갈 수 있다. 여기서 조금 더 개선해보면, 자신보다 작은 숫자와 큰 숫자를 각각 별도로 가지고 있으면 편할 것이다. 여기서 조금 더 생각해보면, 숫자 자체는 의미가 없고 숫자끼리의 대소 관계에만 의미가 있음에 착안하여 알고리즘을 개선할 수 있다.

 

위와 같은 사고 과정을 거치는 것이 이상적이긴 하며, 실제로는, (다행히?) DP로 풀어야겠다는 생각이 먼저 들기는 했다. N <= 100이지만 완전탐색은 불가능한 범위에서 느낌을 조금 받았고, 앞 줄에 누가 있든 뒤에 오는 사람들을 줄 세우는 문제는 공통적으로 반복된다는 subproblem이 존재한다는 느낌을 조금 받았다.

 

그럼 이제 본격적으로 DP 테이블을 정의해보자. 크기의 대소만 중요하고 숫자 자체의 크기는 중요하지 않다는 점, 그리고 작은 숫자와 큰 숫자를 각각 별도로 가지고 있으면 편할 것이라는 점, 두 가지 지점을 고려하면 3차원 DP 테이블을 만들 수 있다. f(g, s, x) = 현재 줄의 숫자가 x이고, x보다 큰 숫자가 g개, x보다 작은 숫자가 s개 있을 때 지그재그 서기의 경우의 수라고 정의할 수 있다. 그리고 바로 다음 줄을 기준으로, 증가하는 방향으로 줄을 세울 지, 감소하는 방향으로 줄을 세울 지에 대해 각각이 별도로 저장되어야 하므로 이러한 DP 테이블은 2개 필요하다.

그런데 여기서 x는 과연 필요한가? 아니다. 자기보다 큰 숫자의 개수와 자기보다 작은 숫자의 개수를 알고 있으면 x는 사실 필요치 않다. 그러니까, 현재 줄의 숫자가 무엇이든지 간에, 다음 줄부터 채워나간다고 할 때 현재 줄의 숫자보다 큰 숫자의 개수와 작은 숫자의 개수만 알고 있으면 된다는 것이다. 결국 2차원 DP 테이블이 2개 있으면 된다.

 

이제는 점화식을 세워보자. DP1을 증가 테이블, DP2를 감소 테이블이라고 하면, 점화식은 다음의 과정을 거쳐 작성된다.

 

DP1[g][s]
= 현재 줄의 숫자보다 큰 숫자가 g개, 작은 숫자가 s개 있고
다음 줄이 증가해야 할 때 지그재그 서기의 경우의 수

DP2[g][s]
= 현재 줄의 숫자보다 큰 숫자가 g개, 작은 숫자가 s개 있고
다음 줄이 감소해야 할 때 지그재그 서기의 경우의 수

 

→ 현재 줄의 숫자보다 큰 숫자를 오름차순으로 G1, G2, ..., Gg, 현재 줄의 숫자보다 작은 숫자를 오름차순으로 두었을 때 S1, S2, ..., Ss이라고 하면, 바로 다음 줄에는 G1, G2, ..., Gg만 올 수 있다(DP1 테이블을 채우는 중이니까, 바로 다음 줄은 지금 줄의 숫자보다 큰 숫자가 와야한다).

→ 설명의 편의를 위해 '현재 줄' 상태에서 숫자를 x라고 하고 가능한 숫자를 오름차순으로 정렬하여 다음과 같이 표현하자. S1, S2, ..., Ss, x, G1, G2, ..., Gg

→ 만약 '다음 줄'에 G1이 왔다면? '그 다음 줄'은 '다음 줄'에 비해 감소해야 한다. 그러면 그 감소하는 지그재그 서기의 경우의 수를 고려하면 된다. 즉 DP2[G1보다 큰 수의 개수][G1보다 작은 수의 개수]가 되는 것이다. 그런데 다음 줄에는 G1뿐만 아니라 G1, G2, ..., Gg가 올 수 있으므로 이들에 대해 각각 큰 수의 개수와 작은 수의 개수를 고려하여 반복문을 돌려주면 된다. 물론 G*보다 큰 수든 작은 수이든 개수를 셀 때에는, x는 이미 사용된 숫자이므로 제외해야 한다.

 

import java.util.Scanner;

public class Main {
    final static int R = 1_000_000;

    static long[][] dp1;
    static long[][] dp2;

    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();

        if (n == 1) {
            System.out.println(1);
            return;
        }

        dp1 = new long[n][n];
        dp2 = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp1[i][j] = dp2[i][j] = -1;
            }
        }

        dp1[1][0] = 1;
        dp1[1][1] = 1;
        dp1[1][2] = 1;
        dp2[0][1] = 1;
        dp2[1][1] = 1;
        dp2[2][1] = 1;

        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += f1(n - 1 - i, i) + f2(n - 1 - i, i);
            sum %= R;
        }
        System.out.println(sum);
    }

    static long f1(int greater, int smaller) { // ASC
        if (dp1[greater][smaller] != -1) return dp1[greater][smaller];
        if (greater == 0) return 0;

        long sum = 0;
        for (int i = 0; i < greater; i++) {
            sum += f2(greater - 1 - i, smaller + i);
            sum %= R;
        }

        return dp1[greater][smaller] = sum;
    }

    static long f2(int greater, int smaller) { // DSC
        if (dp2[greater][smaller] != -1) return dp2[greater][smaller];
        if (smaller == 0) return 0;

        long sum = 0;
        for (int i = 0; i < smaller; i++) {
            sum += f1(smaller + greater - 1 - i, i);
            sum %= R;
        }

        return dp2[greater][smaller] = sum;
    }
}

 

풀이에 도움을 준 이야호와 채완이에게 고마움을 표한다.