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

78번 부녀회장이 될 테야

---

내가 떠올린 풀이 해설

a층의 b호에 살려면 자신의 아래층(a - 1)의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다를 보고 점화식을 세워야 한다. 0층의 사람들은 i호에 i명이 살고 있다고 한다. arr[0][r] = r 모든 층의 1호는 0층 1호부터 1명이어서 모든 층이 1명이다. arr[j][1] = 1 a - 1층의 1호부터 b호까지의 점화식은 arr[j][r] = arr[j][r - 1] + arr[j - 1][r]이다. 

---

정확한 풀이

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

public class Baek2775 {
	static int k, n;
	static int[][] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int i = 0; i < T; i++) {
			k = Integer.parseInt(br.readLine());
			n = Integer.parseInt(br.readLine());
			arr = new int[15][15];
			for(int j = 1; j < 15; j++) {
				for(int r = 1; r < 15; r++) {
					arr[0][r] = r;
					arr[j][1] = 1;
					arr[j][r] = arr[j - 1][r] + arr[j][r - 1];
				}
			}
			System.out.println(arr[k][n]);
		}
	}
}

---

79번 다리 놓기

---

내가 떠올린 풀이 해설

이 문제는 M개의 사이트에서 N개를 선택하는 문제로 변경할 수 있다. 겹치지 않게 하려면 동쪽에서 N개를 선택한 후 서쪽과 동쪽의 가장 위쪽의 사이트에서부터 차례대로 연결할 수 밖에 없기 때문이다. 조합 문제로 변형해 풀 수 있다. 조합 점화식은 많은 문제에서 응용되기 때문에 꼭 알고 있어야 한다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1010 {
	static long[][] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		arr = new long[31][31];
		for(int i = 0; i <= 30; i++) {
			arr[i][0] = 1;
			arr[i][i] = 1;
			arr[i][1] = i;
		}
		for(int i = 2; i <= 30; i++) {
			for(int j = 1; j < i; j++) {  // 고르는 수 개수가 전체 개수를 넘을 수 없다 .
				arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; // 조합 점화식 
			}
		}
		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());
			System.out.println(arr[m][n]);
		}
	}
}

---

오늘의 회고

오늘은 조합 문제 2문제를 풀었습니다. 어렵지 않고 기본 문제였고 점화식을 세우는 방법에 대해 학습할 수 있었습니다. 조합 점화식은 꼭 이해하고 암기가 되어 있어야할 것 같습니다. 장마라 습하고 눅눅해서 불쾌지수가 높아지는데 다들 파이팅입니다.