2023.01.14 코딩 테스트 공부 기록 입니다.

🤖문제 : 2xn 타일링 Lv2

프로그래머스 2xn 문제 링크

😎풀이

def solution(n):
    memory = [0 for _ in range(n)]
    memory[0] = 1
    memory[1] = 2
    
    for i in range(2, n) :
        memory[i] = memory[i-2] + memory[i-1]
        
        if i%1000 == 0 :
            memory[i] = memory[i]%1000000007
            memory[i-1] = memory[i-1]%1000000007
            
    return memory[n-1]%1000000007

👩‍🏫접근 방식

Dynamic Programming

1. 위치 k까지 타일을 놓는 방법은 고정되어 있음. 즉, l번째 타일의 종류가 k까지 타일을 놓는 방식에 영향을 미치지 않음.
2. 따라서, k의 타일을 구할 때 필요한 k-1, k-2, ... 정보들은 계산 후 재 계산이 필요 없음.
3. 따라서, 메모리를 생성하고 연산 정보를 담아 놓음.

fibonacci sequence

1. 각 위치 k에서 놓을 수 있는 타일의 종류는 2개임.
   • 세로로 놓는 것은 1칸 앞으로 간다고 생각 할 수 있음.
   • 가로로 놓는 것은 2칸 앞으로 간다고 생각 할 수 있음.
2. k-1과 k-2까지 쌓은 개수의 합이 k를 결정함.

Modulo(=나머지 연산)의 특징

1. dynamic programming으로만 풀면 시간 초과 발생.
2. 마지막 결과에 1000000007으로 나누라는 것은 결과값이 엄청 크다는 것.
3. 숫자가 크다면 길이 n이 길어질 수록 연산과정에서 시간이 소요 되므로 중간에 나머지로 나눠주는 것인 연산을 빠르게 해줄 수 있음.
4. 따라서, 1000번에 한번씩 나머지 연산을 해주어 연산하는 숫자의 크기를 줄여줌.

Modulo 연산에 대한 추가 설명

• 중간에 Modulo 연산을 하는 것이 결과에 영향을 미치지 않는 이유가 뭘까.
• 이를 구체화 하면, "모든 연산을 한 후 나머지를 구하는 것"과 "각 연산마다 나머지를 구하고 더하는 것" 이 왜 같은가. 로 변환할 수 있고 이를 수식으로 표현하면 아래와 같습니다.

• (1)과 (2)가 있을 때 (3)을 유도 할 수 있는가에 대한 문제로 변환할 수 있습니다.
  $a_{1} \mod b = c_{1} \Leftrightarrow a_{1}=k_{1}b + c_{1}\\ a_{2} \mod b = c_{2} \Leftrightarrow a_{2}=k_{2}b + c_{2}\\$

• 따라서, 중간에 Modulo 연산을 해도 정답엔 문제가 없게 됩니다.

감사합니다.