11727. 2×n 타일링 2

문제

백준 11727번 2×n 타일링 2

---

풀이

아주 기본적인 다이나믹 프로그래밍 문젠데 약간 응용된 문제였다.
처음엔 2×n이 어떻게 생겨먹은건지 이해하느라 시간이 좀 걸렸다.

이런 문제를 풀때 나는 이렇게 직접 그림을 그려본다.

한 3-4단계까지 그려보면 보통 규칙이 나온다. (가끔 빼먹는 케이스가 있어서 풀다가 읭..? 하긴 하지만..)

하나하나 그려보고, 빼먹은 것도 추가하고, 숫자 이리저리 지지고 볶았더니 다음과 같은 규칙을 찾았다.

n이 홀수일 때: 이전 값 * 2 - 1
n이 짝수일 때: 이전 값 * 2 + 1

n = int(input())
dy = [0] * (n+1)
dy[1] = 1
for i in range(2, n+1):
    dy[i] = dy[i-1] * 2 + 1 if i % 2 == 0 else dy[i-1] * 2 - 1
print(dy[n] % 10007)

처음엔 이렇게 리스트를 썼는데 좀 더 메모리를 적게 쓸 수 있지 않을까해서 리스트대신 변수로 고쳐봤다.

n = int(input())
res = 1
for i in range(2, n+1):
    res = res * 2 + 1 if i % 2 == 0 else res * 2 - 1
print(res % 10007)

똑았같다. 왜일까??? 너무 큰 수를 저장해서?? 그래서 다시 고쳐봤다. 작은수로.

n = int(input())
res = 1
for i in range(2, n+1):
    res = (res * 2 + 1) % 10007 if i % 2 == 0 else (res * 2 - 1) % 10007
print(res)

똑같다. 연산이 추가돼서 그런듯하다.