TIL

조합을 사용하는 알고리즘 문제를 2개 풀었다.

백준 11050번: 이항 계수 1

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

이항계수란?

조합론에서 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다

파스칼의 삼각형

위키 백과:
https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95

파스칼의 삼각형(Pascal's triangle)은 수학에서 이항계수를 삼각형 모양으로 배열한 것이다.

파스칼의 삼각형은 조합으로 이런식으로 나타낼 수 있다.

이 공식이 조합의 대표적인 공식이다
또한 nCn= nC1= 1 이라고 한다.

이를 재귀를 이용 해 구현한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st= new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		int result= BC(n,m);
		
		bw.write(String.valueOf(result));
		bw.flush();
		bw.close();
	}
	
	static int BC(int n,int m) {
		
		if(n==m||m==0) {
			return 1;
		}
		//nC0=nCn=1
        
		return BC(n-1,m-1)+BC(n-1,m);
		//n+1 C r+1 = nCr +nCr+1
	}
}

백준 1010번: 다리 놓기

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

이 문제도 조합을 쓰는 것이라 한다.
n= 13, m= 29 이면 29C13 을 하면 된다..

29개의 도착점 중에 13개를 뽑는 것인데
도중에 엇갈리고 겹치는 길이 생기는 경우의 수가 있어도 중복으로 처리하기 때문에 문제 없다고 한다..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main{
	
	static int[][] dp=new int[30][30]; //최대 입력값이 30이다.
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int t= Integer.parseInt(br.readLine());
		
	
		for(int i=0;i<t;i++) {
			StringTokenizer st= new StringTokenizer(br.readLine());
			int n=Integer.parseInt(st.nextToken());
			int m=Integer.parseInt(st.nextToken());
			int result=bridge(m,n);
			bw.write(result+"\n");
		}
		bw.flush();
	}

	static int bridge(int n, int m) {
	
		if(dp[n][m] > 0) {
			return dp[n][r]; 
		}
		//이미 값이 저장되어 있으면 그대로 반환 한다.
        
		if(n == m || m == 0) {
			return dp[n][m]= 1;
		}
		//nC0=nCn=1
        
		return dp[n][m] = bridge(n - 1, m - 1) +bridge(n - 1, m);
        //n+1 C r+1 = nCr +nCr+1 
        //구한 값을 dp에 저장한다.
	}
}

수학 개념을 모르니 잘 모르겠다.
고등학교때 배운 것을 어렴풋이 생각해내 이해하는 정도..