백준 9095 1, 2, 3 더하기
1.
테이블 정의
•
D[i] → 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수 구하기
2.
점화식 찾기
•
D[i] = D[i - 1] + D[i - 2] + D[i - 3]
3.
초기값 설정
•
D[1] = 1
•
D[2] = 2
•
D[3] = 4
Python
num = int(input())
arr = [0] * 10001
arr[0] = 1
arr[1] = 2
arr[2] = 4
for _ in range(1, num+1):
t = int(input())
for i in range(3, t+1):
arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3]
print(arr[t-1])
Python
복사
JAVA
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] arr = new int[10001];
arr[0] = 1;
arr[1] = 2;
arr[2] = 4;
for (int j = 1; j <= num; j++) {
int t = sc.nextInt();
for (int i = 3; i <= t; i++) {
arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
}
System.out.println(arr[t-1]);
}
}
}
Java
복사