백준 20152(Game Addiction) - Python(파이썬) - 다이나믹

20152번: Game Addiction

예제 설명

(8,8) -> (4,4) 를 가는 방법의 수는 (4,4) -> (8,8) 로 가는 방법의 수랑 동일하다. 

이 방법의 수는 y>x인 곳은 침수되어서 갈 수 없다고 하였으므로 (4,5),(4,6),,, 이 모든 값은 0이라고 볼 수 있다.

(4,4)의 점을 (0,0)이라고 가정하고, (8,8)의 점을 (4,4)라고 가정하고나서 표를 작성하면 다음과 같다

 

점화식 | if j>=i : 

      dp[j][i] = dp[j-1][i] + dp[j][i-1]

j \ i	4=0	5=1	6=2	7=3	8=4
4=0	1	1	1	1	1
5=1	0	1	2	3	4
6=2	0	0	2	5	9
7=3	0	0	0	5	14
8=4	0	0	0	0	14

풀이 설명
① h,n을 받은 후에 hn=(h와 n의 절댓값) +1이라고 가정
② dp를 hn * hn 구조로 배열 선언
③ j=0인 값은 모두 1로 초기화
④ 그 후에는 점화식(if j>=i: dp[j][i]=dp[j-1][i]+dp[j][i-1]) (i : 1 - hn , j : 1-hn ) 

Python(파이썬)

import sys
h,n = map(int,sys.stdin.readline().split())
#둘의 절댓값 +1 
hn = abs(h-n)+1
dp = [[0]*(hn) for _ in range(hn)]

//1로 초기화
for i in range(hn):
    dp[0][i]=1
//점화식
for i in range(1,hn):
    for j in range(1,hn):
    	#i값이 j보다 크거나 같은 경우
        if i>=j:
            dp[j][i]=dp[j-1][i]+dp[j][i-1]


print(dp[hn-1][hn-1])

Java(자바)

자바에서는 조심하기 !! dp를 long[][] 배열로 선언하기!!!

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine()," ");
        int h = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int hn = Math.abs(h-n)+1;
        long[][] dp = new long[hn][hn];
        for(int i=0;i<hn;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<hn;i++){
            for(int j=1;j<hn;j++){
                if(j>=i)
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }

        System.out.println(dp[hn-1][hn-1]);
    }
}