백준 14494(다이나믹이 뭐에요?) - Python(파이썬) - 다이나믹

문제 설명 

이런 원리로 (2,1)의 점 1, (3,1)의 점 1, (2,2)의 점 3이 세점을 더해서 5가 만들어지는 것이다.

즉 , 5 (3,2) = 1(2,1) + 1(3,1) + 3(2,2)

이걸 dp 그래프안에 넣었다고 가정해서 점화식으로 풀면

 dp[m][n] = dp[m-1][n-1]+dp[m-1][n] + dp[m][n-1] 

풀이 방법
① m=1, n = 1인 지점은 모두 1이다. 갈 수 있는 방법은 무조건 일이다

1	1	1	1
1
1
1

② 따라서 m의 값이 증가에 따라 for문 해서 1부터 n까지 루프문 돌린다. 
③ 단, 수가 커지기 때문에 array값을 구할 때 마다 1,000,000,007 나눈 나머지 값을 구한다.

Python(파이썬)

import sys
n,m = map(int,sys.stdin.readline().split())
#n,m 행렬 이므로 모두 다 1로 초기화
array =[[1]* n for _ in range(m)]

for i in range(1,m):
    for j in range(1,n):
        array[i][j]=(array[i-1][j-1]+array[i-1][j]+array[i][j-1])%1000000007

print(array[m-1][n-1])

Java(자바)

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

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 n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        long[][] array = new long[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0 || j==0){
                    array[i][j]=1;
                }
            }
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                array[i][j]= (array[i-1][j]+array[i][j-1]+array[i-1][j-1])%1000000007;
            }
        }
        System.out.println(array[n-1][m-1]);
    }
}