S3 11727. 2×n 타일링 2

문제 보기 :  11727번: 2×n 타일링 2

---

문제

• 정답률 : 58%

---

작성 코드

arr = [1]*(1001)
for i in range(1,1001):
    if i%2==1:
        arr[i]=arr[i-1]*2 + 1
    else:
        arr[i]=arr[i-1]*2 - 1
    arr[i] %= 10007

T = int(input())
print(arr[T-1])

---

풀이

1 : 1, 2: 3, 3: 5. 4: 11, 5: 21, 6: 21, 7: 43...의 순서로 증가하는 규칙을 가진다. 

1*2와 2*1만 있을 때는 피보나치 수열로 해결하면 됐는데 [1, 3, 5, 11, 21, 43,.. ] 이 수열은 규칙을 찾기가 좀 어려웠다.

그래서 제곱에 차수 빼는 방법, 이전 값 모두 더해서 다음 값으로 두는 방법 등등 다양한 방법들로 구해보려고 했으나 다 실패하던 중,
홀수 차수에선 이전 값에 2배수 후 +1, 짝수 차수에서는 이전 값에 2배수후 -1을 하면 된다는 규칙을 찾았다. 

그래서 최댓값인 1001만큼의 배열을 두고 이 규칙을 적용해 알고리즘을 만들어둔 뒤, input을 받아 해당 값을 찾았다.