[백준 2193 이친수 문제] PYTHON

 

신기한 문제였다.

아무리 머리를 굴려도 좋은 방법이 생각이 안나 모든 경우를 list에 append해서

append한 리스트가 input값이 됐을 때 global로 RESULT를 만들어서 +1을 하게했다.

하지만 역시나 시간초과가 됐다.

RESULT=0
def sol(result_list,i,t):
    tmp_list1=result_list[:]
    if(i==t):
        global RESULT
        RESULT+=1
        return
    if(tmp_list1[i-1]==1):
        tmp_list1.append(0)
        return sol(tmp_list1,i+1,t)
    else:
        tmp_list=tmp_list1[:]
        tmp_list.append(1)
        tmp_list1.append(0)
        return sol(tmp_list1,i+1,t),sol(tmp_list,i+1,t)
if __name__ == "__main__":
    t=int(input())
    result_list=[1]
    sol(result_list,1,t)
    print(RESULT)

 

답은 맞춘거 같아 그냥 5 넣어보고 10 넣어보고 했는데

넣어 볼수록 피보나치 수열과 같은 값이 나왔다.

설마하고 피보나치 문제 code를 넣어보니 clear....

 

나중에 사람들의 풀이를 보니 1일때 2일때 3일때 연속되는 규칙이 있었다.

아래를 보면 2의 10, 3의 맨 앞자리를 뗀 00,01이 4번째 10 후로 동일하게 나온다.

이 규칙은 5번째도 마찬가지다. 이걸 어떻게 발견했는지..

앞으로 패턴에 대해 생각하고 문제를 푸는 습관을 길러야겠다.

 

1

1

2

10

3

100

101

4

1010

1000

1001

5

10100

10101

10010

10000

10001