[Algorithm] ๐Ÿฆ˜์™ธ๋ฐœ ๋›ฐ๊ธฐ

0. ๋ฌธ์ œ

๋•…๋”ฐ๋จน๊ธฐ๋ฅผ ํ•˜๋‹ค ์งˆ๋ฆฐ ์žฌํ•˜์™€ ์˜ํ›ˆ์ด๋Š” ๋•…๋”ฐ๋จน๊ธฐ์˜ ๋ณ€์ข…์ธ ์ƒˆ๋กœ์šด ๊ฒŒ์ž„์„ ํ•˜๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด ๊ฒŒ์ž„์€ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด n*n ํฌ๊ธฐ์˜ ๊ฒฉ์ž์— ๊ฐ 1๋ถ€ํ„ฐ 9 ์‚ฌ์ด์˜ ์ •์ˆ˜๋ฅผ ์“ด ์ƒํƒœ๋กœ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค. ๊ฐ ์ฐจ๋ก€์ธ ์‚ฌ๋žŒ์€ ๋งจ ์™ผ์ชฝ ์œ— ์นธ์—์„œ ์‹œ์ž‘ํ•ด ์™ธ๋ฐœ๋กœ ๋›ฐ์–ด์„œ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜ ์นธ์œผ๋กœ ๋‚ด๋ ค๊ฐ€์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด ๋•Œ ๊ฐ ์นธ์— ์ ํ˜€ ์žˆ๋Š” ์ˆซ์ž๋งŒํผ ์˜ค๋ฅธ์ชฝ์ด๋‚˜ ์•„๋ž˜ ์นธ์œผ๋กœ ์›€์ง์ผ ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ค‘๊ฐ„์— ๊ฒŒ์ž„ํŒ ๋ฐ–์œผ๋กœ ๋ฒ—์–ด๋‚˜๋ฉด ์•ˆ ๋ฉ๋‹ˆ๋‹ค.
๊ท ํ˜•์„ ์žƒ์–ด์„œ ๋‹ค๋ฅธ ๋ฐœ๋กœ ์„œ๊ฑฐ๋‚˜ ๋„˜์–ด์ ธ๋„ ๊ฒŒ์ž„์—์„œ ์ง‘๋‹ˆ๋‹ค๋งŒ, ์žฌํ•˜์™€ ์˜ํ›ˆ์ด๋Š” ์ Š๊ณ  ํ™œ๊ธฐ์ฐจ๊ธฐ ๋•Œ๋ฌธ์— ์™ธ๋ฐœ๋กœ ๋›ฐ์–ด๋‹ค๋‹ˆ๋Š” ๊ฒƒ์€ ์•„๋ฌด๊ฒƒ๋„ ์•„๋‹™๋‹ˆ๋‹ค. ๋‹ค๋งŒ ๊ฑฑ์ •๋˜๋Š” ๊ฒƒ์€ ์ฃผ์–ด์ง„ ๊ฒŒ์ž„ํŒ์— ์‹œ์ž‘์ ์—์„œ ๋์ ์œผ๋กœ ๊ฐ€๋Š” ๋ฐฉ๋ฒ•์ด ์กด์žฌํ•˜์ง€ ์•Š์„ ์ˆ˜๋„ ์žˆ๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ๊ทธ๋ฆผ (a)์˜ ๊ฒŒ์ž„ํŒ์—์„œ๋Š” ์‚ฌ๊ฐํ˜•์œผ๋กœ ํ‘œ์‹œ๋œ ์นธ๋“ค์„ ํ†ตํ•ด ๋์— ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, ์ˆซ์ž๊ฐ€ ํ•˜๋‚˜ ๋ฐ”๋€ ๊ทธ๋ฆผ (b)์—์„œ๋Š” ๊ทธ๋Ÿด ์ˆ˜๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค.
๊ฒŒ์ž„ํŒ์ด ์ฃผ์–ด์งˆ ๋•Œ ์™ผ์ชฝ ์œ„์˜ ์‹œ์ž‘์ ์—์„œ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜์˜ ์‹œ์ž‘์ ์— ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”.

์ž…๋ ฅ
์ž…๋ ฅ์˜ ์ฒซ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ˆ˜ C(C <= 50)๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ ์ค„์—๋Š” ๊ฒฉ์ž์˜ ํฌ๊ธฐ n(2 <= n <= 100)์ด ์ฃผ์–ด์ง€๊ณ , ๊ทธ ํ›„ n์ค„์— ๊ฐ n๊ฐœ์˜ ์ˆซ์ž๋กœ ์™ผ์ชฝ ์œ„๋ถ€ํ„ฐ ๊ฐ ์นธ์— ์“ฐ์ธ ์ˆซ์ž๋“ค์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์˜ค๋ฅธ์ชฝ ์•„๋ž˜ ์žˆ๋Š” ๋ ์  ์œ„์น˜์—๋Š” 0์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

์ถœ๋ ฅ
๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค ํ•œ ์ค„๋กœ, ์‹œ์ž‘์ ์—์„œ ๋ ์ ์œผ๋กœ ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ์„ ๊ฒฝ์šฐ "YES"๋ฅผ, ์•„๋‹ ๊ฒฝ์šฐ "NO"๋ฅผ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค. (๋”ฐ์˜ดํ‘œ ์ œ์™ธ)

1. ๋ฌธ์ œ ๊ฐ„๋‹จ ํ•ด์„

๊ฐ ์นธ์— ์ ํ˜€ ์žˆ๋Š” ์ˆซ์ž๋งŒํผ ์˜ค๋ฅธ์ชฝ ๋˜๋Š” ์•„๋ž˜์ชฝ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์Œ ๋ชฉ์ ์ง€์— ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์—ฌ๋ถ€๋ฅผ ๊ฐ€๋ ค์„œ ์ถœ๋ ฅํ•˜๊ธฐ

2. ์•„์ด๋””์–ด

๋ฉ”๋ชจ์ด์ œ์ด์…˜ : ์ €์žฅํ•ด๋†“๊ณ  ์‚ฌ์šฉํ•˜๊ธฐ (์ค‘๋ณต ์—ฐ์‚ฐ ๊ฐ์†Œ)

3. ํ•ต์‹ฌ ํ’€์ด

1) ๋ฉ”๋ชจ์ด์ œ์ด์…˜

if(cache[y][x] != -1)
			return cache[y][x];
		
int jumpSize = board[y][x];
		
return cache[y][x] = jump(y+jumpSize, x) | jump(y, x+jumpSize);

4. ์ฝ”๋“œ

import java.util.*;

public class DP_EX_1 {
	static int n;
	static int board[][] = new int[100][100];
	static int cache[][] = new int[100][100];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		while(tc > 0) {
			n = sc.nextInt();
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					board[i][j] = sc.nextInt();
					cache[i][j] = -1;
				}
			}
			
			if(jump(0,0) == 1)
				System.out.println("YES");
			else
				System.out.println("NO");
			
			tc--;
		}
	}
	
	static int jump(int y, int x) {
		if(y>=n || x>=n) return 0;
		if(y == n-1 && x == n-1) return 1;
		
		if(cache[y][x] != -1)
			return cache[y][x];
		
		int jumpSize = board[y][x];
		
		return cache[y][x] = jump(y+jumpSize, x) | jump(y, x+jumpSize);
	}

}

5. ๊ฒฐ๊ณผ

์„ฑ๊ณต~

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ