find(현재 계단의 인덱스, 앞에 2개 계단의 상태)

이렇게 탐색합니다.

밟은 계단은 1으로 밟지 않은 계단은 0으로 생각합니다.

앞의 2개 계단의 상태는 01, 10, 11 3가지만 나옵니다.

01이면 바로 앞의 것은 밟았고, 2개 앞의 것은 밟지 않았습니다.
10이면 바로 앞 계단은 밟지 않았고, 2개 앞의 것은 밟았습니다.
11이면 바로 앞 계단과, 2개 앞 계단 모두 밟았습니다.

문제의 조건에 따라,
1.두 계단을 연속으로 밟지 않고, 뛰어넘을 수 없습니다.(1001과 같은 상황은 존재 할 수 없습니다.)
2. 3개의 계단을 연속으로 밟을 수 없습니다.(1110과 같은 상황은 존재할 수 없습니다.)

그러면
1. 현재 탐색할 인덱스에서 현재 계단을 밟아야 하는가 아닌가
2. 다음 상태는 어디로 가는가

이 두가지를 결정 해주면 됩니다.

01 -> 이번 계단을 밟을 수도 있고, 계단을 밟지 않을 수도 있습니다.   -> 010 또는 011

        이번 계단을 밟지 않으면 010이 되고, find(a+1, 10),

        이번 계단을 밟으면 011이 되고 find(a+1,11) + 현재 계단의 값

10 -> 두칸을 연속으로 안밟을 수는 없으므로(00), 이번 계단은 무조건 밟아야 합니다. -> 101

         find(a+1,01) + 현재 계단의 값(밟았기 때문에 더해줌)

11 -> 세칸을 연속으로 밟을 수 없으므로(111), 이번 계단은 무조건 밟지 않습니다. -> 110

         find(a+1,10)

그리고 이전 2개의 계단의 상태는 2진수를 10진수로 바꾼 것으로 생각합니다.

01->1, 10->2, 11->3 

다시 말해 b는 1,2,3 세 가지만 존재합니다.

현재 인덱스 : a    과거 2개의 계단의 밟았는지 여부: b

find(a,1) = max( find(a+1,2)+현재 계단의 값, find(a+1,3))

find(a,2) = find(a+1,1)+현재 계단의 값

find(a,3) = find(a+1, 2)

이렇게 점화식을 만들었습니다.

다만 54%까지 가고 에러가 난 것은 문제의 세 번째 조건, 마지막 계단은 무조건 밟아야 된다를 잘못 구현했기 때문입니다.

마지막 계단의 인덱스를 n이라고 한다면

n-2    n-1    n

1       0        1

0       1        1

이렇게 2가지 값 중 큰 값을 선택해야 합니다.

그리고 문제의 조건을 충족(00이나 111은 나올 수 없음)시켜야 하기 때문에,

n-3번째 값은 점화식을 따르지 않고 맨 마지막 계단을 밟는 위의 2가지 경우 중 큰 값을 택하도록 해야 합니다.

f(n-3,1)

n-5    n-4    n-3    n-2    n-1    n

0         1         0      1       0       1

0         1         1      0       1       1

두가지 중 큰 값,

f(n-3, 2)

n-5    n-4    n-3    n-2    n-1    n

1        0         1       1       0       1

1        0         1       0       1       1

두가지 중 큰 값,

f(n-3, 3)

n-5    n-4    n-3    n-2    n-1    n

1        1        0       1       0       1

1        1        0       0       1       1   -----> 연속으로 두 칸을 안 뛸수는 없기 때문에 00이 나오면 틀립니다.

                                                              그러나 아래의 코드에는 이 상황을 고려하고 있기 때문에 틀렸습니다.

이 부분을 고쳐서 문제를 해결했습니다.

굉장히 간단한 점화식 인 것 같았는데 생각보다 너무 오래 헤매서, 푼 기념으로 글을 써놓고 갑니다.

도움이 되었으면 좋겠습니다.