Algorithm/백준
[백준] Silver I. 쉬운 계단 수
미네구스
2024. 6. 15. 17:15
https://www.acmicpc.net/problem/10844
사용 알고리즘
- 다이나믹 프로그래밍
풀이
1차원 으로 생각해서 틀린 풀이
public class Main {
static int n;
static int [] d = new int[102];
static int [] s = new int[102];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
d[0] = 0;
d[1] = 9;
s[0] = 0;
for(int i = 2; i <= n; i++) {
s[i] = i - 1;
d[i] = (2 * (d[i-1] - 1) + s[i]) % 1000000000;
}
System.out.println(d[n]);
}
}
정답
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
테이블: d[i][j]: 길이가 i고 마지막 자릿수가 j인 계단의 수
점화식: d[i][j] = d[i-1][j-1] + d[i-1][j+1]
*/
public class Main {
static int n;
static int [][] d = new int[102][10];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
for(int i = 1; i <= 9; i++) {
d[1][i] = 1;
}
for(int i = 2; i <= n; i++){
for(int j = 0; j <= 9; j++) {
if (j > 0) d[i][j] += d[i-1][j-1]; // j가 9일때 edge case 처리
if (j < 9) d[i][j] += d[i-1][j+1]; // j가 0일때 edge case 처리
d[i][j] %= 1000000000;
}
}
long res = 0;
for(int i = 0; i <= 9; i++) {
res += d[n][i];
res %= 1000000000;
}
System.out.println(res);
}
}
회고
테이블
- d[i][j]: 길이가 1고 마지막 자릿수가 j인 계단의 총합
점화식
- d[i][j] = d[i-1][j-1] + d[i-1][j+1], 단 i,j는 유효 범위 내여야 함.
n = 2일때
d[2][0] = d[1][1] // 예외처리
d[2][1] = d[1][0] + d[1][2]
d[2][2] = d[1][1] + d[1][3]
d[2][3] = d[1][2] + d[1][4]
d[2][4] = d[1][3] + d[1][5]
d[2][5] = d[1][4] + d[1][6]
d[2][6] = d[1][5] + d[1][7]
d[2][8] = d[1][7] + d[1][9]
d[2][9] = d[1][8] // 예외처리
n = 3일떄
d[3][0] = d[2][1]
d[3][1] = d[2][0] + d[2][2]
...
d[3][9] = d[2][8]
이런 규칙으로 이어지게 된다.
맨 처음에 n = 1일떄 초기화를 해주어야 하므로,
for(int i = 1; i <= 9; i++) {
d[1][i] = 1;
}
이렇게 값을 1로 할당해준다.
for(int i = 2; i <= n; i++){
for(int j = 0; j <= 9; j++) {
if (j > 0) d[i][j] += d[i-1][j-1]; // j가 9일때 edge case 처리
if (j < 9) d[i][j] += d[i-1][j+1]; // j가 0일때 edge case 처리
d[i][j] %= 1000000000;
}
}
그리고, 해당 자릿수에 맞는 값을 업데이트 해주는데 범위를 조심해야 한다. d[i][-1]이나 d[i][10]은 제외해야 하므로, 두가지 케이스를 예외처리 해준다.
long res = 0;
for(int i = 0; i <= 9; i++) {
res += d[n][i];
res %= 1000000000;
}
System.out.println(res);
그리고, 마지막에 모든 값을 더해주면 끝난다.
음.. 일단 계속 풀어봐야겠다