Baekjoon 2193 이친수 JAVA

https://www.acmicpc.net/problem/2193

2193번: 이친수

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%202193

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 이진수에서 특정 조건을 만족하는 수를 이친수라 하는데

자릿수가 주어졌을 때 해당 자릿수에 해당하는 이친수를 개수를 구하는 문제다.

​

이친수는 0으로 시작하지 않는다 (1로 시작!)

이친수는 11을 부분 문자열로 갖지 않는다 (1이 연속으로 들어오지 않는다)

​

해당 문제는 dp를 이용해서 해결했으며 5자릿수까지 경우의 수를 나열해 보았더니 특정 규칙을 찾을 수 있었다.

​

먼저 앞의 경우의 수 중에서 뒷자리가 0인 경우 0과 1을 추가한 결과를 가질 수 있고

뒷자리가 1인 경우 0만 추가한 결과를 가질 수 있다.

​

위의 그림처럼 진행되므로 6의 자리까지 해보면 결국

0으로 끝나는 건 5개, 1로 끝나는 건 3개인 걸 알 수 있으며,

원래는 0과 1로 끝나는 거에 대해 각각 구하고 더하는 방법이 있지만 어차피 결국 합해지기 때문에

1, 2의 값을 저장해둔 뒤, 3부터 dp[i] = dp[i-1] + dp[i-2] 해당 점화식을 이용하여 계산하면 되고

int형으로 할 경우 90자릿수에서 음수 값이 나오기 때문에 long형으로 dp 배열을 사용하여야 한다.