1.
테이블 정의
•
d[i][j] → j로 끝나는 i자리 이친수의 개수
2.
점화식
•
j = 0 일 때 : d[3][0] = d[2][0] + d[2][1]
•
j = 1 일 때 : d[3][1] = d[2][0]
3.
초기값 정하기
•
d[1][0] = 0
•
d[1][1] = 1
Python
num = int(input())
arr = [[0] * 10 for _ in range(num+1)]
arr[1][0] = 0
arr[1][1] = 1
for i in range(2, num+1):
arr[i][0] = arr[i-1][0] + arr[i-1][1]
arr[i][1] = arr[i-1][0]
print(arr[num][0] + arr[num][1])
Python
복사
JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
long[][] arr = new long[100][2];
arr[1][0] = 0;
arr[1][1] = 1;
for (int i = 2; i <= num; i++) {
arr[i][0] = arr[i-1][0] + arr[i-1][1];
arr[i][1] = arr[i-1][0];
}
System.out.println(arr[num][0] + arr[num][1]);
}
}
Java
복사