[BOJ/DP] 백준 1146 - 지그재그 서기 (Java)

1146 - 지그재그 서기

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

문제

N명의 학생들을 줄을 세우려고 함
1. 맨 앞줄: 아무나
2. 둘째 줄: 아무나
3. 셋째 줄: 첫째 줄에 서 있는 사람 < 둘째 줄에 서 있는 사람 -> 둘째 줄에 서 있는 사람 > 셋째 줄에 서 있는 사람
/ 첫째 줄에 서 있는 사람 > 둘째 줄에 서 있는 사람 -> 둘째 줄에 서 있는 사람 < 셋째 줄에 서 있는 사람
4. 넷째 줄부터는 둘째 줄과 셋째 줄 비교 
=> N번째 줄은 N-2번째 줄과 N-1번째 줄 비교
ex. 1이 가장 작은 사람, N이 가장 큰 사람(같은 키 X) => 13254 / 32514

=> 총 몇가지 경우의 수?

입력: 학생 수 N (1 <= N <= 100)
출력: 총 경우의 수 % 1,000,000 나눈 나머지

---

풀이

• 지그재그 수열: a1 < a2 > a3 < a4 > a5 < ... or a1 > a2 < a3 > a4 < a5 > ...

 

• 파스칼 삼각형 이용해 조합 구현
  • $nCk = (n-1)C(k-1) + (n-1)C(k)$ 
    
    • $nC0$ = 1: n개 중 0개 고르는 경우 항상 1개 (고르지 X 경우)
    • $nCn$ = 1: n개 중 n개 고르는 경우 항상 1개 (전부 다 고르는 경우)
  • `arr[i][j]`: $iCj$ -> i개 중 j를 선택하는 경우의 수

int[][] arr = new int[N + 1][N + 1];
arr[0][0] = 0;
for (int i = 1; i <= N; i++) {
    arr[i][0] = arr[i][i] = 1;
    for (int j = 1; j < i; j++) {
        arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j]) % MOD;
    }
}

 

• `dp[n]`: 길이 n인 지그재그 수열의 개수
• 중앙에 어떤 수 k 있다고 가정
  • 중앙 기준 왼쪽: j개 / 오른쪽: i - 1 - j개 => left(j개) + [k] + right(i - 1 - j개)
  • => 길이 n인 지그재그 수열의 개수: 절반은 ... <로 끝나는 수열, 절반은 ... >로 끝나는 수열
  • ex. ... < k > ... -> k가 최댓값
    • 왼쪽 수열의 끝: ... < k -> 작게 끝나는 수열만 유효 => 전체의 절반
    • 오른쪽 수열의 끝: ... > k -> 작게 시작하는 수열만 유효 => 전체의 절반
    • => 지그재그 수열 중에서도 특정 방향으로 끝나는/시작하는 경우에만 사용
•  `dp[i] = (dp[i] + arr[i - 1][j] * lt % MOD * rt % MOD) % MOD` 
  • `dp[i] += arr[i - 1][j] * lt * rt` -> 오버플로우 방지: 곱셈 순서대로 중간마다 % MOD
  • `arr[i - 1][j]`: ${i-1}Cj$ => 전체 i개 수 중 중앙값(k)를 제외한 i - 1개 수 중 j개 -> 왼쪽 / i - 1 - j개 -> 오른쪽 배치
  • `int lt = (dp[j] + 1) / 2`: 왼쪽 수열 중 끝 방향이 적절(조건 만족)한 경우만
  • `int rt = (dp[i - 1 - j] + 1) / 2`:오른쪽 수열 중 끝 방향이 적절(조건 만족)한 경우만

long[] dp = new long[N + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= N; i++) {
    for (int j = 0; j < i; j++) {
        long lt = (dp[j] + 1) / 2;
        long rt = (dp[i - 1 - j] + 1) / 2;
        dp[i] = (dp[i] + arr[i - 1][j] * lt % MOD * rt % MOD) % MOD;
    }
}

---

코드

import java.io.*;

// 지그재그 서기
public class boj_1146 {
    static final int MOD = 1_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[][] arr = new int[N + 1][N + 1];
        arr[0][0] = 0;
        for (int i = 1; i <= N; i++) {
            arr[i][0] = arr[i][i] = 1;
            for (int j = 1; j < i; j++) {
                arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j]) % MOD;
            }
        }

        long[] dp = new long[N + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j < i; j++) {
                long lt = (dp[j] + 1) / 2;
                long rt = (dp[i - 1 - j] + 1) / 2;
                dp[i] = (dp[i] + arr[i - 1][j] * lt % MOD * rt % MOD) % MOD;
            }
        }

        System.out.println(dp[N]);
    }
}