[백준 BOJ][DP] 2193 이친수

2193_이친수

 

링크

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

 

풀이

 

 

조건을 보면 0으로 시작하지 않고, 1이 연속으로 올 수 없습니다.

그럼 마지막 자리(0, 1)를 담을 수 있는 DP[N][2]를 만든다고 가정합시다.

N이 1이면 0이 올 수 없으므로 DP[1][0] = 0, DP[1][1] = 1이 됩니다.

 

 

그리고 0으로 올 수 있는 건 마지막 자리가 0과 1 다 가능하고, 1로 올 수 있는 건 마지막 자리가 0인 경우 밖에 없습니다.

 

이 조건을 이용해서 점화식을 정의해 보겠습니다.

DP[N][0] = DP[N-1][0] + DP[N-1][1]

DP[N][1] = DP[N-1][0]

입니다. 이렇게 코드를 짜고 마지막에 DP[N][0] + DP[N][1]을 출력하면 됩니다. 하지만 더 최적화 할 수 있습니다.

 

두 번째 식에 N 대신 N-1을 대입해 봅시다.

DP[N-1][1] = DP[N-2][0]

첫 번째 식 DP[N][0] = DP[N-1][0] + DP[N-1][1]에 대입해 봅시다.

DP[N][0] = DP[N-1][0] + DP[N-2][0]

 

보시면 [0]으로만 표현돼 있습니다.

DP[N] = DP[N-1] + DP[N-2]

최적화하면 최종 점화식이 나오는데, 피보나치 수열이네요.

 

n이 90이하니까 int 범위를 벗어납니다. long long으로 DP[91]을 선언해 줍시다.

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

//2193_이친수 #include <iostream> using namespace std;   long long DP[91] = { 0, 1, 1 };   int main() {     int n;     int i;       cin >> n;       for (i = 3; i <= n; ++i) {         DP[i] = DP[i - 1] + DP[i - 2];     }       cout << DP[n] << endl;       return 0; } Colored by Color Scripter

cs