[Java] BOJ 2193번 이친수

2193번: 이친수

---

풀이

DP를 이용해서 해결했습니다.

 

문제의 조건에서 이친수의 맨 앞에는 0이 올 수 없으므로 각 자릿수 별 이친수의 개수를 보면

한자리 = 1 → 1개

두자리 = 10 → 1개

세 자리 = 100, 101 → 2개

네 자리 = 1000, 1001, 1010 → 3개

다섯 자리 = 10000 10001 10010 10100 10101 →5개

...

N자리 = N - 1자리의 개수 + N - 2자리의 개수가 됩니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static int N;
	public static long[] memo = new long[91];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		memo[1] = 1;
		memo[2] = 1;
		memo[3] = 2;
		for (int i = 4; i <= N; ++i) {
			memo[i] = memo[i - 1] + memo[i - 2];
		}
		
		System.out.println(memo[N]);
	}
}

---

pyo7410/Algorithm