[백준/JAVA] 10844번: 쉬운 계단 수
🔺 문제
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
import java.util.*;
import java.io.*;
public class Main {
static long mod = 1000000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long[][] D = new long[N + 1][11];
// 길이가 1일 때 만드는 높이 i로 끝나는 계단 수의 모든 경우의 수
for(int i = 1 ; i <= 9 ; i++) {
D[1][i] = 1;
}
for(int i = 2 ; i <= N ; i++) {
D[i][0] = D[i-1][1]; // 높이가 0이면 바로 앞 단계가 1이어야 올 수 있음
D[i][9] = D[i-1][8]; // 높이가 9면 바로 앞 단계가 8이어야 올 수 있음
// 높이가 1~8이면 자신보다 한 단계 위 아래 모두에서 올 수 있음
for(int j = 1 ; j <= 8 ; j++) {
D[i][j] = (D[i-1][j-1] + D[i-1][j+1]) % mod;
}
}
long sum = 0;
for(int i = 0 ; i < 10 ; i++) {
sum = (sum + D[N][i]) % mod;
}
System.out.println(sum);
}
}
|
cs |
✅ 해결 아이디어
✔ DP - 점화식
→ D[N][H] : 길이가 N인 계단에서 높이 H로 종료되는 계단 수를 만들 수 있는 경우의 수
(높이에 따라 다른 점화식)
🔺 다른 풀이들
- Top-Down 방식도 올려놓으심
[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]
www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 저번 문제인 1로 만들기보다 쉬운 편이다. 몇가지 규칙만 알면 되니 한 번
st-lab.tistory.com
- 상세한 설명
백준 10844번 (DP) - 쉬운 계단 수 (JAVA) 문제 풀이
10844번: 쉬운 계단 수 (acmicpc.net) 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ✏️ 문제 🔐 문제 해결 1. 테이블 정의 dp[i][j]는 길이가 i이고, j로 시
iseunghan.tistory.com
[백준/10844/Java] 쉬운계단수
문제링크 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이
smartpro.tistory.com
💬 느낀 점
2차원 배열...... 점화식을 구하는 것은 익숙하지 않은 듯허다...
DP 과정 따르면서 점화식을 잘 찾아봐야디,,,
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 7/6 |
(참고)
✔ Do it 알고리즘 코딩테스트 자바편