아이디어

• 문제는 부분 최적 구조를 가진다. 필요한 변수를 고려해보자.
  • y, x: 좌표
    • (1, 1)부터 (y, x)까지 오는 경우의 수를 세어야 한다.
  • c: (y, x)까지 거쳐온 오락실 수
    • (y, x)까지 오기 까지 거쳐온 오락실 수가 모두 다를 수 있다.
  • m: (y, x)까지 거쳐온 오락실 중 가장 높은 번호
    • m 이하 번호의 오락실은 갈 수 없다.
• 즉, 동적 테이블은 4차원 테이블이 된다.
• 만약 (y, x)가 오락실이 아니면 c, m에 상관 없이 (모든 c, m에 대해) 왼쪽, 위쪽의 경우의 수를 더한다.
• 만약 (y, x)가 X번 오락실이면, 거쳐온 오락실 수가 c-1인 왼쪽 위쪽의 모든 m < X에 대한 경우를 더한다.
• 각 c에 대해 구하는 값은 모든 m에 대한 memo[m][c][N][M]의 합이다.
• 이러한 풀이는 $O(C^2 NM)$의 시간, 공간복잡도를 가진다. 그러나 C, N, M이 모두 50 이하이므로 가능하다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int N, M, C;
    static int[][] map;
    static int[][][][] memo;    // [m: 현재까지 방문한 가장 큰 번호][c: 현재까지 방문한 오락실 수][y][x]
    
    static final int MOD = 1_000_007;
    
    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        N = Integer.parseInt(tk.nextToken());
        M = Integer.parseInt(tk.nextToken());
        C = Integer.parseInt(tk.nextToken());

        map = new int[N+1][M+1];
        for (int i=1; i<=C; i++) {
            tk = new StringTokenizer(rd.readLine());
            int y = Integer.parseInt(tk.nextToken());
            int x = Integer.parseInt(tk.nextToken());
            map[y][x] = i;
        }
        
        memo = new int[C+1][C+1][N+1][M+1];
        
        memo[map[1][1]][map[1][1] != 0 ? 1 : 0][1][1] = 1;
        
        for (int y=1; y<=N; y++) {
            for (int x=1; x<=M; x++) {
            	if (map[y][x] == 0)
            		for (int c=0; c<=C; c++) for (int m=0; m<=C; m++)
            			memo[m][c][y][x] = (memo[m][c][y][x] + memo[m][c][y-1][x] + memo[m][c][y][x-1]) % MOD;
               	else
                   	for (int c=1; c<=C; c++) for (int m=0; m<map[y][x]; m++)
                   		memo[map[y][x]][c][y][x] = (memo[map[y][x]][c][y][x] + memo[m][c-1][y-1][x] + memo[m][c-1][y][x-1]) % MOD;
        	}
        }
        
        for (int c=0; c<=C; c++) {
        	int sum = 0;
        	for (int m=0; m<=C; m++) {
        		sum = (sum + memo[m][c][N][M]) % MOD;
        	}
            sb.append(sum).append(' ');
        }
        System.out.println(sb);
    }
}

메모리 및 시간

• 메모리: 48700 KB
• 시간: 712 ms

리뷰

• 4차원 테이블이라니 무섭다 호달달
  • 비트마스크 테이블 이후의 충격
• 모듈러 식 실수하지 않도록 조심