import java.util.Scanner;
public class Main {
static final long mod = 1000000000;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long d[][] = new long[n + 1][10];
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]; // L+1만 해야됨
d[i][9] = d[i - 1][8]; // L-1만 해야됨
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 += d[n][i];
}
sum %= mod;
System.out.println(sum);
}
}
D[N][L] = 길이가 N인 계단 수. 마지막으로 사용한 수가 L
N-1번째에 올 수 있는 수는 L-1, L+1이다.
즉, 경우의 수는 D[N-1][L-1] + D[N-1][L+1]이다.
하지만 L=0인 경우 L-1을 할 수 없고, L=9인 경우 L+1을 할 수 없기 때문에 예외 처리를 해야 한다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long d[][] = new long[n + 1][2];
d[1][1] = 1;
d[1][0] = 0;
for(int i = 2; i <= n; i++) {
d[i][0] = d[i - 1][1] + d[i - 1][0];
d[i][1] = d[i - 1][0];
}
System.out.println(d[n][0] + d[n][1]);
}
}
D[N][L] = N자리 이친수. 마지막 수가 L.
초기값은 가장 짧은 이친수는 길이가 1이다.
D[1][0]은 이친수는 0으로 시작하지 않으므로 0이다.
D[1][1]은 1이다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int d[] = new int[n];
for(int i = 0; i < n; i++) {
d[i] = 1;
for(int j = 0; j < i; j++) {
if(a[j] < a[i]) {
d[i] = Math.max(d[i], d[j] + 1);
}
}
}
int answer = d[0];
for(int i = 0; i < n; i++) {
if(answer < d[i]) {
answer = d[i];
}
}
System.out.println(answer);
}
}
D[i] = A[1], ..., A[i]까지 수열이 있을 때 A[i]을 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
D[i] = max(D[j]) + 1 이다.
j의 범위는 i보다 작고, j번째 수가 i번째 수 보다 작아야 한다.
import java.util.*;
public class Main {
static int a[];
static int d[];
static int v[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
d = new int[n];
v = new int[n];
for(int i = 0; i < n; i++) {
d[i] = 1;
v[i] = -1;
for(int j = 0; j < i; j++) {
if(a[j] < a[i] && d[i] < d[j] + 1) {
d[i] = d[j] + 1;
v[i] = j;
}
}
}
int answer = d[0];
int index = 0;
for(int i = 0; i < n; i++) {
if(answer < d[i]) {
answer = d[i];
index = i;
}
}
System.out.println(answer);
go(index);
System.out.println();
}
static void go(int index) {
if(index == -1) {
return;
}
go(v[index]);
System.out.print(a[index] + " ");
}
}
D[i] = A[1], ..., A[i]까지 수열이 있을 때 A[i]을 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
V[i] = A[i]의 앞에 와야 하는 수의 인덱스. 즉, A[i]의 앞에는 A[V[i]]가 와야 길이가 가장 길다
정답을 출력할 때는 V[i]를 역추적하면 된다.