[백준] 단계별로 풀어보기(단계:17,정수론 및 조합론,JAVA)1010번, 다리놓기

문제 링크

1010번: 다리 놓기

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제는 서쪽에 있는 사이트만큼 동쪽에 있는 사이트를 고르는 문제입니다.

전체 몇 개에서 몇개를 구한다는 것은 이항계수를 뜻합니다. = nCm

그래서 예제 입력을 살펴보면

서쪽 사이트 : 2개 동쪽 사이트 2개 = 1

서쪽 사이트 : 1개 동쪽 사이트 5개 = 5

서쪽 사이트 : 13개 동쪽 사이트 29개 = 67863915 

이항계수란 이항정리로 전개하였을 때 조합의 가짓수를 나타내는 것으로공식은 nCm 일 때

n!/m!(n-m)!          0≤k≤n

0                        k<0

0                        k>n

예를 들어₄C₂ = 4!/2!(4-2)! = (4×3×2×1)/(2×1)(2×1) = 6

하지만 알고리즘으로 표현할 때 재귀를 통해 모든 숫자를 곱하고 약분할 경우 시간초과가 발생할 수 있습니다.그래서 저는 이항계수의 표로 불리는 파스칼 표를 사용하여 알고리즘을 작성하였습니다.

출처: https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98(위키백과)

이항 계수 - 위키백과, 우리 모두의 백과사전

파스칼 표를 보면 자신 위에 두 수의 합이 이항 계수의 값이 됩니다.

예를 들어 ₄C₂ = ₃C₁ + ₃C₂  = 3 + 3  = 6이 되는 형태입니다.

파스칼표를 구성하기위해 메모이제이션 배열을 사용하였으며 크기는 문제에서 다리를 놓을 수 있는 사이트가 최대 30이므로 배열[31][31]로 구성하여 만들었습니다.

알고리즘으로 표현하자면

nCm = n-₁Cm-₁ + n-₁Cm 으로 

num[n][m] = num[n-1][m-1] + num[n-1][m]을 구하는 식으로 사용하였습니다.

• 메모이제이션 배열 num을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• for문을 통해서 각 줄마다 받은 입력값들에 대한 이항계수를 구하도록 하였습니다.
• StringTokenizer를 통해 띄어쓰기 기준으로 숫자를 나누어 저장하였습니다.
• 이항계수를 구하는 함수 binomialCoefficient를 만들었습니다.
• 함수를 통해 이항계수를 받아 BufferedWriter에 저장하였습니다.
• BufferedWriter을 사용하여 저장된 결과를 출력하였습니다.

• 위에 알고리즘을 토대로 메모이제이션 및 재귀를 통하여 binomialCoefficient을 구성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static Integer num[][] = new Integer[31][31];	//메모이제이션 배열
	static int index;	//입력 개수
	static int N,K;	//오른쪽,왼쪽
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //-----------입력값 저장------------
    	StringTokenizer st;
    	index = Integer.parseInt(br.readLine());
    	int result;
    	for(int i=0;i<index;i++) {
    		st = new StringTokenizer(br.readLine()," ");
        	K = Integer.parseInt(st.nextToken());
        	N = Integer.parseInt(st.nextToken());
        	result = binomialCoefficient(N,K);	//이항계수 구하기
        	bw.write(result + "\n");	//결과 BufferedWriter에 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
	}
    //----------이항 계수 구하는 함수--------------
	public static int binomialCoefficient(int N, int K) {
		if(K==0 || N==K)
			return 1;
		if(num[N][K]==null) 
			num[N][K] = binomialCoefficient(N-1, K-1) + binomialCoefficient(N-1, K);
		
		return num[N][K];
	}
}