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문제를 풀었습니다. 첫 번째 문제는 난이도가 높지 않은 문제였고, 두 번째 문제는 문제를 이해하는데 시간이 많이 걸렸습니다. 프로그래머스 교육도 진행 중이라 앞의 개념에 대해 까먹을 것 같습니다. 이제는 교육도 듣고 앞에 문제 개념도 복습하고 그 개념에 대한 문제를 푸는 식으로 공부를 진행해야 될 것 같습니다. 하면 할수록 저는 알고리즘이 어려운 것 같습니다. 알고리즘 잘하고 싶다. 꾸준히 공부하겠습니다.
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
| 백준) 수학(피타고라스), 이분 탐색 (0) | 2022.07.16 |
|---|---|
| 백준) 수학, 이분 탐색 (0) | 2022.07.13 |
| Do it! 알고리즘 코딩 테스트(85번 ~ 86번) (0) | 2022.07.05 |
| Do it! 알고리즘 코딩 테스트(83번 ~ 84번) (0) | 2022.07.01 |
| Do it! 알고리즘 코딩 테스트(82번) (0) | 2022.06.30 |
