[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. ๊ฒฐ๊ณผ
์ฑ๊ณต~
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐ฆ์ธ๋ฐ ๋ฐ๊ธฐ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-์ธ๋ฐ-๋ฐ๊ธฐ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค