[알고리즘] 백준. #1904 01타일

동적 계획법 파트의 또 하나의 문제이다. 

알고리즘 수업을 수강한 아는 형의 말이 떠올랐다. 알고리즘은 결국 '점화식'만 잘 짜면 되는거야..

알고리즘을 잘 알지 못하는 나로서는 이게 맞는 말인지 아닌지 감이 잘 오지 않는다 하하..

근데 적어도 동적 계획법에 한해서는 점화식만 잘 짜도 반은 먹고 들어가는 거 같다. 

 

이번 문제는 이렇다. 00과 1이라는 타일이 있는데 n이라는 수가 주어졌을 때 이 두 종류의 타일을 이어 붙일 수 있는 경우의 수를 말한다. 00은 타일 2개가 붙어있는 꼴이다. 

 

표로 정리해 보면 다음과 같다.

n	1	2	3	4
타일 연속체	1	00, 11	001, 100, 111	0011, 1001, 1111, 0000, 1100
붙일 수 있는 타일 종류의 수	1	2	3	5

뭔가 패턴이 보일듯 말듯 하다..

 

그렇다. n=3일 때부터 보면 tile(n) = tile(n-1) + tile(n-2), (n>=3, tile(1) = 1, tile(2) = 2)이다. 

사실 이 문제는 계단을 오르는 문제로 환원해 볼 수 있다. 

 

2개 짜리 타일 00과 1개짜리 타일 1이 있고, 이 둘은 완전히 구분된다.

(*만일 01과 1처럼 겹치는 부분이 있었다면, 좀 더 고민해봐야 했을 것이다. )

따라서 다음 그림처럼 전체 n층의 계단을 올라가는데 2칸씩 올라갈 수 있고, 1칸씩 올라갈 수 있다. 이 두 방법을 조합해 n층까지 올라갈 수 있는 방법의 개수를 구하는 문제와 같다고 할 수 있다.

 

 

 

또 점화식을 구하는 한 가지 팁을 드리자면, 보통 패턴이 n번째 값을 구하기 위해 n-1, n-2, n-3, ... 이전의 값으로 구한 내용들을 이용해서 풀 수 있다. 

 

예를 들어 4층까지 올라가는 방법의 수를 구한다 할 때(n = 4), 우리는 3층까지 올라갈 수 있는 방법의 수와 2층까지 올라갈 수 있는 방법의 수만 알면 된다. 왜냐하면, 3층까지 이미 올라갔을 때 구한 모든 경우에 수에서 1칸만 올라가면 4층이 되기 때문이다. 마찬가지로 2층까지 올라간 모든 경우의 수에서 두칸을 올라가면 4층에 도달할 수 있다. 

 

여기서 3층까지 올라간 방법의 수(편의상 tile(3)), 2층까지 올라간 방법의 수(tile(2))는 마지막으로 올라간 계단 수가 각각 1, 2로 다르기에 겹치는 부분이 없다. 또 tile(1)은 이미 tile(2)와 tile(3)에 그 경우의 수가 포함되었기에 tile(4)를 계산할 때 구할 필요가 없다. 

 

3층까지 이미 올라갔을 때 구한 모든 경우에 수에서 1칸만 올라가면 4층이 되기 때문이다. 

원래 재귀적으로 함수를 call하는 방식으로 구현했었는데, 실행시간이 너무 오래걸려서 시간초과가 되었다. 따라서 지난번 피보나치 함수와 마찬가지로 리스트에 초깃값을 주고, 이 값들을 이용해 점화식으로 n번째 값까지 구한 후 n번째 값을 출력해 주도록 하였다.

n = int(input())

mem = [0, 1,2] #mem[0]은 indexing할 때 편의를 위해 임의로 값을 넣어 주었다. n=1일 때 mem[1]로 쓰기 위함

def tile2(n):
    global mem
    if n == 1 or n == 2:
        print(mem[n])
    
    else: 
        for i in range(3, n+1):
            mem.append((mem[i-1] + mem[i-2])%15746) #문제에서 결과 값을 15746으로 나눠준 나머지 값을 요구 하였다. 
            						#C나 Java 등에서 int 자료형의 표현 크기 제한 때문인 것으로 보인다. 
        print(mem[n])
tile2(n)

 

점화식으로 구현한 코드, 메모이제이션 없이 순수 재귀 호출로만 진행하면 너무 느리기에 결과값을 기록할 리스트(mem)을 따로 만들어 메모이제이션을 적용하였다. 

*이 코드는 백준 저지를 통과하지 못했습니다.

n = int(input())

mem = [-1]*(n+1)

mem[1] = 1 # 1

mem[2] = 2 # 00, 11

def tile(n):
    global mem
    if n == 1 or n == 0:
        return mem[n]
    
    if mem[n] == -1:
        mem[n] = tile(n-1) + tile(n-2)
        return mem[n]
    else:
        return mem[n]
print(tile(n)%15746)