[JAVA] 백준 1010 다리 놓기

1010번: 다리 놓기 (acmicpc.net)

1010번: 다리 놓기

 

 

풀이 과정 

 

[수학] 순열, 조합 공식 총정리 (tistory.com)

[수학] 순열, 조합 공식 총정리

 

- M개에서 N개를 선택해야 하며 서로 중복되면 안됨 -> 조합 이용 

- nCr -> 서로 다른 n개에서 r개를 뽑는 것 

 

- nCr = n-1Cr-1 + n-1Cr

- nC0 = nCn =1

 

- 조합은 하나의 원소를 선택할 경우 + 하나의 원소를 선택하지 않을 경우 이 둘의 합을 나타냄 

[Java] 조합 Combination (tistory.com)

[Java] 조합 Combination

 

ex)

(1,2,3) 중에서 2개를 뽑는 조합 -> 3C2

  - (1,X)  : 1을 뽑는 경우 (하나의 원소를 선택할 경우)

  - (X,X) : 1을 뽑지 않는 경우 (하나의 원소를 선택하지 않는 경우)

 

- 1을 뽑은 경우 나머지 (2,3) 중 1개를 선택해야 함  -> 2C1

- 1을 뽑지 않은 경우 (2,3) 모두 선택해야 함  -> 2C2

- 이를 바탕으로 더 이상 쪼개지지 않을 때 까지 , 즉 c=nC0=1이 될 떄까지 구한다면 nCr을 구할 수 있음

 

- 3C2 = 2C1 + 2C2+.... 3C0 = 1이 될 때까지 재귀호출을 통해 구현 

- 재귀를 통해 호출을 하다가 r==0이 될 경우 , 즉 r개를 다 뽑은 경우에는 더 이상 선택의 여지가 없으므로 1을 리턴

- 전체 개수 n이 뽑아야 할 개수 r과 같아졌다면  다 뽑는 것 말고 선택의 여지가 없으므로 1을 리턴 

- 그 이외에는 원소를 선택할 경우 + 선택하지 않을 경우 둘의 합을 계속 재귀로 호출

 

public static int combination(int n , int r)
{

	if(n==r ||r==0) 
    {
    	return 1;
    }
    
    return combination(n-1, r-1) + combination(n-1, r);
}

 

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 int combination(int n ,int r)
    {
        if(n==r||r==0)
        {
            return 1;
        }
        
        return combination(n-1,r-1)+combination(n-1,r);
    }
    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 num = Integer.parseInt(br.readLine());
        
       
        for(int i=0; i<num; i++)
        {
        	StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            
            bw.write(combination(m,n)+"");
            bw.newLine();
        }
        
        bw.flush();
        bw.close();
        
        
    }
}

 

 

 

 

- 메모이제이션(Memoization)을 이용하여 동적 계획법으로 활용

- 이전에 풀었던 자료를 저장해놨다가 빠르게 처리 

- dp [][] 배열을 사용하여 이미 계산된 값은 다시 계산하지 않고 중복 계산을 피함 

- 입력값 n과 r에 맞는 조합 결과가 dp[n][r]에 저장되고 출력됨 

 

[백준] 1010번 : 다리 놓기 - JAVA [자바] (tistory.com)

[백준] 1010번 : 다리 놓기 - JAVA [자바]

 

 

 

정답 

 

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];
	
    public static int combination(int n ,int r)
    {
    	//이미 계산된 값일 경우 
    	if(dp[n][r]>0)
    	{
    		return dp[n][r];
    	}
    	
        if(n==r||r==0)
        {
            return dp[n][r] = 1;
        }
        
        return dp[n][r]=combination(n-1,r-1)+combination(n-1,r);
    }
    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 num = Integer.parseInt(br.readLine());
        
       
        for(int i=0; i<num; i++)
        {
        	StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            
            bw.write(combination(m,n)+"");
            bw.newLine();
        }
        
        bw.flush();
        bw.close();
        
        
    }
}