[Python] 1793 - 타일링 (실버2)

1. 문제 설명

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

1793번: 타일링

 

---

2. 아이디어

dp를 많이 써보지 않은 때라서 꽤 오랫동안 고민했었던 문제였다.

웃긴 건 풀긴 풀었는데 수학 문제 처럼 풀어버렸다가 다시 dp로 풀이해서 통과했다.

내가 처음 풀이한 방식은 top down 방식이고, 이 포스팅을 쓰면서 bottom up 방식 코드도 추가했다.

 

처음에 패턴을 못 찾아서 직접 모든 경우를 구하다 보니 일정한 규칙이 있음을 찾아냈다.

어째 피보나치 수열을 풀 때 dp를 쓰던 것과 흡사하게 생겼다 했더니 비슷한 풀이 방법으로 풀린다.

 

---

3. 코드

1. 수학으로 풀기 (이러면 사실 cache가 필요가 없다 ㅋㅋㅋ...)

cache = [0]*251

def calc_case(n):
    if n <= 2:
        return cache[n]
    if cache[n] == 0:
        if n % 2 == 1:
            cache[n] = 2 * calc_case(n - 1) - 1
        elif n % 2 == 0:
            cache[n] = 2 * calc_case(n - 1) + 1
    return cache[n]


def solution():
    cache[0] = 1
    cache[1] = 1
    cache[2] = 3
    while True:
        try:
            n = int(input())        
            print(calc_case(n))
        except:
            break

solution()

 

2. top down

cache = [0]*251

def calc_case(n):
    if n <= 2:
        return cache[n]
    if cache[n] == 0:
        cache[n] = calc_case(n-2)*2 + calc_case(n-1)
    return cache[n]

def solution():
    cache[0] = 1
    cache[1] = 1
    cache[2] = 3
    while True:
        try:
            n = int(input())        
            print(calc_case(n))
        except:
            break

solution()

 

3. bottom up

cache = [0] * 251
cache[0] = 1
cache[1] = 1
cache[2] = 3

for i in range(3, 251):
	cache[i] = cache[i-1] + 2 * cache[i-2]
 
while True:
	try:
    	n = int(input())
        print(cache[n])
    except:
    	break