아이디어

• 모든 칸 (y, x)에 대해, 단어의 글자 수 Z에 대해 인덱스 Z-2에서 역순으로 현재 위치와 갈 수 있는 위치의 글자가 단어의 i번과 i+1번이라면 memo[i][y][x]에 memo[i+1][new_y][new_x]만큼 경우의 수를 더한다.
• 모든 칸에 대해 memo[0][y][x]의 합이 정답이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;
import java.util.Map;
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, K, Z, ans;
	static char[][] map;
	static char[] word;
	static int[][][] X;
	
	// up right down left
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, 1, 0, -1};
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		K = Integer.parseInt(tk.nextToken());

		map = new char[N][];
		for (int y=0; y<N; y++) {
			map[y] = rd.readLine().toCharArray();
		}
		word = rd.readLine().toCharArray();
		Z = word.length;
		
		X = new int[Z][N][M];
		for (int y=0; y<N; y++) {
			for (int x=0; x<M; x++) {
				X[Z-1][y][x] = 1;
			}
		}

		for (int z=Z-2; z>=0; z--) {
			for (int y=0; y<N; y++) {
				for (int x=0; x<M; x++) {
					for (int d=0; d<4; d++) {
						for (int k=1; k<=K; k++) {
							int ny = y + dy[d] * k;
							int nx = x + dx[d] * k;
							if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
							if (map[ny][nx] == word[z+1] && map[y][x] == word[z]) {
								X[z][y][x] += X[z+1][ny][nx];
							}
						}
					}
				}
			}
		}
		
		for (int y=0; y<N; y++) {
			for (int x=0; x<M; x++) {
				ans += X[0][y][x];
			}
		}
		
		System.out.println(ans);
	}
}

메모리 및 시간

• 메모리: 19516 KB
• 시간: 316 ms

리뷰

• 오랜만의 PS, DP
• 5중 루프가 최선이었나..?