[코딩테스트] 백준(BAEKJOON) - 이항 계수 2(Java, 11051번)

안녕하세요~

 

너무 오랜만에 코딩테스트 문제를 푸네요...

사실 SQLD 준비한답시고 코딩테스트 문제를 안풀었는데..

SQLD로 시원하게 말아먹은 느낌입니다 😊😊

DB관련 공부한것도 글을 올리고 싶은데 시간이 너무 없네요 헤헤

 

과연 저의 미래는 어떨지 너무나도 무섭네요.

 

오랜만에 다시 풀어볼 문제는 이항 계수 2입니다.

문제 링크 입니다.

 

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

11051번: 이항 계수 2

 

이항계수 문제는 사실 규칙을 쉽게 찾을 수 있기에 금방 풀 수 있었습니다.

다만 한 가지 생각 못한 부분이 있었습니다.

먼저 제가 작성한 코드입니다.

 

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


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
			
			String line=bf.readLine();
			int N=Integer.parseInt(line.split(" ")[0]);
			int K=Integer.parseInt(line.split(" ")[1]);
			
			int dp[][]=new int[N+1][N+1];
			
			for(int i=1;i<=N;i++)
			{
				for(int j=0;j<=i;j++)
				{
					if(j==1)
						dp[i][j]=i%10007;
					else if(j==i||j==0)
						dp[i][j]=1;
					else
						dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%10007;
				}
			}
			System.out.println(dp[N][K]);


			
	}

}

네~ 이렇게 풀었습니다.

 

다만 여기서 주의 할 점은 M이 0일경우 입니다.

계속 오답으로 나와서 찾아보니 M이 0일경우는 0이아니라 1로 처리 되더군요~

 

이 부분 유의하신다면 푸실 수 있을거라 생각됩니다. 그리고 제가 풀었던 풀이과정 남겨드리겠습니다~

 

해당 예시를 통해서 보면 

- 3C2=2C1+2C2

- 4C2=3C1+3C2

ㄴ> 즉 NCM=N-1CM-1+N-1CM 의 합이라는걸 알 수 있습니다.

 

DP테이블에다 적용시키면 되겠습니다.

 

감사합니다. :D