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

87번 2 x n 타일링

---

내가 떠올린 풀이 해설

크기가 2 x 1일 때부터 2 x 2... 하나씩 높여가면서 경우의 수를 구하면 규칙이 나온다. 그 규칙을 이용해서 점화식을 구하면 되는 문제이다. 점화식은 arr [n] = arr[n - 1] + arr[n - 2]이다. arr배열을 채울 때마다 10,007으로 % 연산을 수행해야 한다. 

---

정확한 풀이

import java.util.*;
public class Baek11726 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] arr = new long[n + 1];
		arr[1] = 1;
		arr[2] = 2;
		int mod = 10007;
		for(int i = 3; i <= n; i++) {
			arr[i] = (arr[i - 1] + arr[i - 2]) % mod;
		}
		System.out.println(arr[n]);
	}
}

---

88번 쉬운 계단 수

---

내가 떠올린 풀이 해설

n번째 길이에서 5로 끝나는 계단 수가 있었을 때 이 계단 수의 n - 1의 자리에 올 수 있는 수는 1 차이가 나는 4와 6이다. 이를 이용해 문제를 풀겠다. arr[n][h] : 길이가 n인 계단에서 h 높이로 종료되는 계단 수를 만들 수 있는 경우의 수이다. n에서 계단 높이가 0일 때 계단 수가 되려면 n - 1에서는 높이가 1이어야 한다. n에서 계단 높이가 9일 때 계단 수가 되려면 n - 1 에서는 높이가 8이어야 한다. 나머지는 가운데 계단이므로 h + 1, h - 1 양쪽에서 계단 수를 만들 수 있다. 

 

높이에 따른 점화식

•  arr[i][h] = arr[i - 1][h + 1] // h = 0
• arr[i][h] = arr[i - 1][h - 1] // h = 9
• arr[i][h] = arr[i + 1][h - 1] + arr[i - 1][h - 1] // h = 1 ~ 8

arr배열의 값을 초기화한다. 각 높이에서 길이가 1인 계단 수는 모두 1가지이므로 1로 초기화한다. 단, 0으로 시작될 수 없으므로 이때는 0으로 초기화한다. arr 배열을 채울 때마다 1000000000으로 % 연산을 수행한다. arr[n][0] ~ arr[n][9]의 모든 값을 더한 값을 출력한다 n = 2일 때 각 자릿수의 값을 모두 더하면 n = 2의 길이에서 만들 수 있는 모든 계단 수의 경우의 수를 출력할 수 있다.

---

정확한 풀이

import java.util.Scanner;

public class Baek10844 {

	public static void main(String[] args) {
		long mod = 1000000000;
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[][] arr = new long[n + 1][11];
		for(int i = 1; i <= 9; i++) {
			arr[1][i] = 1;
		}
		for(int i = 2; i <= n; i++) {
			arr[i][0] = arr[i - 1][1];
			arr[i][9] = arr[i - 1][8];
			for(int j = 1; j <= 8; j++) {
				arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]) % mod;
			}
		}
		long sum = 0;
		for(int i = 0; i < 10; i++) {
			sum = (sum + arr[n][i]) % mod;
		}
		System.out.println(sum);
	}

}

---

오늘의 회고

오늘은 DP문제 2문제를 풀었습니다. 첫 번째 문제는 난이도가 높지 않은 문제였고, 두 번째 문제는 문제를 이해하는데 시간이 많이 걸렸습니다. 프로그래머스 교육도 진행 중이라 앞의 개념에 대해 까먹을 것 같습니다. 이제는 교육도 듣고 앞에 문제 개념도 복습하고 그 개념에 대한 문제를 푸는 식으로 공부를 진행해야 될 것 같습니다. 하면 할수록 저는 알고리즘이 어려운 것 같습니다. 알고리즘 잘하고 싶다. 꾸준히 공부하겠습니다.