[백준] 2193번 : 이친수

문제

 

 

접근 방식

어떻게 풀어야할지 모르겠어서 일단 각 자리수별로 만들 수 있는

경우들을 직접 나열해보고서 규칙을 찾아보았다.

1 

10

100
101

1000
1001
1010

10000
10001
10010
10100
10101

100000
100001
100010
100100
100101
101000
101001
101010

1000000
1000001
1000010
1000100
1000101
1001000
1001001
1001010
1010000
1010001
1010010
1010100
1010101

 

각 자리수별로 경우의 수를 세어보면 1, 1, 2, 3, 5, 8, 13, ...

이런식으로 증가하는 것을 알 수 있는데 어디서 많이 본거 같다면

생각하는 그 피보나치 수열이 맞다.

 

1과 2의 경우만 초기값을 1로 지정하고

3자리부터 dp[i - 1] + dp[i - 2]를 계산해주면서

테이블을 채워주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		long[] dp = new long[91];

		dp[1] = 1;
		dp[2] = 1;

		for (int i = 3; i <= n; i++) {
			dp[i] = dp[i - 2] + dp[i - 1];
		}

		System.out.println(dp[n]);
	}
}