Do it! 알고리즘 코딩 테스트 (76번 ~ 77번)

76번 이항 계수 1

---

내가 떠올린 풀이 해설

조합에서 가장 기본이 되는 문제이다. 일반 점화식을 이용하면 쉽게 해결할 수 있는 문제이다. n과 k를 입력받고 DP 배열을 선언한다. 배열은 arr [n + 1][n + 1] 그리고 DP 배열의 값을 다음과 같이 초기화한다. arr [i][1] = i -> i 개 중 1개를 뽑는 경우의 수는 i개 arr[i][0] = 1 -> i 개 중 1개도 선택하지 않는 경우의 수는 1개 arr[i][i] = i -> i 개 중 i 개를 선택하는 경우의 수는 1개이다. 점화식으로 DP 배열의 값을 채운다. arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1] 마지막으로 arr [n][k] 값을 출력한다.

---

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek11050 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[][] arr = new int[n + 1][n + 1];
		for(int i = 0; i <= n; i++) {
			arr[i][0] = 1; // i 개에서 1개도 선택하지 않는 경우의 수는 0개 
			arr[i][i] = 1; // i 개에서 모두 선택하는 경우의 수는 1개 
			arr[i][1] = i; // i 개에서 1개 선택 경우의 수는 i개 
		}
		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]);
	}
}

---

---

내가 떠올린 풀이 해설

바로 앞에 문제와 비슷한 문제이다 n의 값이 커지고 결괏값을 10,007로 나눈 나머지를 출력하라는 요구사항이 있다. 모듈러 연산의 특성을 이용해 문제를 풀었다. 모듈러 연산은 덧셈에 관해 위와 같이 각각 모듈러를 하고, 모듈러 연산을 수행한 것과 두 수를 더한 후 수행한 것의 값이 동일하므로 이 문제에서 arr배열에 결괏값이 나올 때마다 모듈러 연산을 수행하는 로직을 추가하면 문제를 해결할 수 있다.

 

모듈러 연산의 특성

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

---

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek11051 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[][] arr = new int[n + 1][n + 1];
		int pow = 10007;
		for(int i = 0; i <= n; i++) {
			arr[i][0] = 1;
			arr[i][i] = 1;
			arr[i][1] = i;
		}
		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]) % pow;
			}
		}
		System.out.println(arr[n][k]);
	}
}

---

오늘의 회고

오늘은 DP 문제를 풀기 위해 먼저 학습해야 되는 조합에 대해서 학습하고 조합에 관련된 기본 문제 2문제를 풀었습니다. DP가 알고리즘 문제 풀이에서 2번째로 중요하다고 들었습니다. 매번 출제되는 문제인 만큼 확실하게 학습하고 넘어가겠습니다.