조합 관련 문제 풀어보기

문제1(브론즈1)

가장 기초적인 문제, 입력 값들의 순열값을 구함

import java.util.*;

public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

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

        for(int i = 0; i <= N; i++){
            D[i][1] = i; // i개중 한개를 뽑는 경우의 수 : i
       		D[i][0] = 1; // i개중 0개를 뽑는 경우의 수 : 1
            D[i][i] = 1; // i개중 i개를 뽑는 경우의 수 : 1
        }
		
        // 밑의 반복문을 보면 i = 1인 경우에는 굳이 DP를 안해도 답이 위 반복문에서 구해짐
        // j = 1부터 i-1까지 
        for(int i = 2; i <= N; i++){
            for(int j = 1; j < i; j++){
                D[i][j] = D[i-1][j] + D[i-1][j-1];
            }
        }
        System.out.println(D[N][K]);
    }
}

우의 문제의 경우 j가 1부터 시작할 필요가 없을것같아 2부터 시작했는데 마찬가지로 정답이였다!

---

문제2(실버2)

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

import java.util.*;

public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

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

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

모듈러 연산을 적용 하면 좀더 문제를 쉽게 풀수 있다

(A mod N + B mod N)mod N = (A + B)mod N;

---

문제3(브론즈1)

점화식 구하는 부분이 상당히 간단함!

---

문제4(실버5)

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

간단한 조합 문제

---

문제5(실버3)

다시한번 풀어보기!!!, 구현은 했으나 코드가 지저분함

---

문제6(골드5)

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

너무 어렵다.. 풀이를 봐도 이해 못한 문제...
위의 문제 이해해서 풀수 있다면
https://www.acmicpc.net/problem/1947
https://www.acmicpc.net/problem/1256

이 두문제도 풀수있게 노력해보자!

---