[코딩테스트] 백준(BAEKJOON) - 다리 놓기(Java, 1010번)

안녕하세요.

4일만에 다시 글을 남기네요.

사실 요즘 현업이 너무 바빠 글을쓸시간도 없고 문제도 못풀고했었습니다.ㅠㅠ

 

이문제는 사실 풀어놓고 글쓰기 귀찮아 오늘 한꺼번에 올리는 문제입니다. 하하~

 

자오늘 만나볼 문제는 다리놓기 입니다.

정말 뭔가~ 수학문제집 푸는 느낌이네요~

문제 바로 만나보시죠~

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

그렇습니다. 이문제도 DP문제입니다.

그러면 이제 제 코드를 만나보시죠~

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
			
			int count=Integer.parseInt(bf.readLine());
			
			for(int i=0;i<count;i++)
			{
				String[] bridge=bf.readLine().split(" ");
				int N=Integer.parseInt(bridge[0]);
				int M=Integer.parseInt(bridge[1]);
				
				long[][] array=new long[N+1][M+1];
				
				for(int j=1;j<=N;j++)
				{
					for(int k=1;k<=M;k++)
					{
						if(j==1)
							array[j][k]=k;
						else
							array[j][k]=array[j-1][k-1]+array[j][k-1];					
					}
					
				}
				System.out.println(array[N][M]);
				
			}
		
	
		
		
	}

}

사실 이문제에 대해서는 점화식..이란 없습니다. 왜냐?!

공책에다가 하나씩 써보다가 규칙을 찾았기 때문이죠~

 

이렇게 표를 만들면서 하나씩 찾다가 (N,M)=(N-1,M-1)+(N,M-1)인걸 확인하실 수 있습니다.

 

그렇습니다!

이번문제는 여기서 간단하게 마무리하겠습니다.

 

감사합니다:D