[do it 알고리즘] 백준11050 (조합)

조합

• 자체로도 자주 출제되며 동적 계획법을 이해하는데 중요
• 점화식을 도출하는 것이 매우 중요
• 기본 지식으로 i C k 이면, k는 (0 ~ i)까지 가능하며 k=0 또는 k=i 이면 1이다.

점화식 도출

1. 특정 문제를 가정
2. 모든 부분 문제가 해결되었다고 가정하고 지금 문제 생각

예시

• 5개 중에 3개를 고르는 5C3
• (1,2,3,4),5가 있으면 괄호안은 이미 선택이 완료된 데이터
• 5를 선택한다면 이미 선택된 데이터 4개중 2개만 골라야 한다. 4C2
• 5를 선택하지 않는다면 이미 선택된 데이터 4개중 3개를 골라야 한다. 4C3
• 즉, 5C3 = 4C2 + 4C3
• D[i][j] = D [i-1][j-1] + D [i-1][j]

문제 설명

풀기 전 생각

• 위에서 얻은 점화식을 활용하여 재귀함수 사용
• 재귀함수를 멈추는 조건 생각
• N < K || N ==0일 때는 계산이 불가하니 0
• N == 1 || K ==0 일때는 1

코드

import java.util.*;
public class Baek11050 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        System.out.println(combi(N, K));
    }
    public static int combi(int N, int K) {
        if(N < K || N==0) {return 0;}
        if(N==1 || K==0){return 1;}
        int result = combi(N-1,K) + combi(N-1,K-1);
        return result;
    }
}

강의 분석

• 2차원 배열을 사용하여 풀이
• k는 0~i까지 가능하므로 D [i][0] = 1, D [i][i] = 1으로 초기화
• 나머지 수들은 점화식으로 채워나가기

강의 코드

import java.util.*;
public class Baek11050{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        int [][] arr = new int[N+1][N+1];

        for(int i = 0; i <= N; i++){
            arr[i][0] = 1;
            arr[i][i] = 1;
        }

        for(int i = 2; i <= N; i++){
            for(int j = 1; j < i; j++){
                arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
            }
        }
        System.out.println(arr[N][K]);
    }
}

예시 : 5C3