[Python Algorithm] 01타일 BOJ #1904

문제

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

1904번: 01타일

 

내 문제 풀이

n = int(input())
if n == 1: print(1)
elif n == 2: print(2)
else:
    memory = [1, 2]
    for i in range(2, n):
        memory.append((memory[i-2] + memory[i-1]) % 15746)
    print(memory[n-1])

👉DP 문제로, 점화식과 메모이제이션 방식을 사용하여 푸는게 포인트!

 

[점화식]

• n == 1 : 1
• n == 2 : 00, 11
• n == 3 : 001, 100, 111
• n == 4 : 0000, 0011, 1001, 1111
• n == 5 : 00001, 00111, 10011, 11001, 11100, 00100, 11111

=> n의 개수 = (n-1)의 개수 + (n-2)의 개수

 

[풀이 설명]

• n이 1 혹은 2의 경우는 반복 연산이 불가하므로 따로 빼서 출력했다.
• 그 외의 경우는 모두 for문을 사용하여 memory 리스트에 값을 누적하여 결과를 구해주었다.

 

💡 피드백

• 비교적 흔한 점화식 구하는 문제라 금방 풀 수 있었다.