[1904] 01타일

2023-03-21 | Algorithms / 백준 문제 풀이 모음 # Python, Sliver 3

백준 문제 풀이

1904번: 01타일

• 해설

    00과 1로만 가능한 조합을 찾는 문제이다.
      
    N이 1~6까지 조합을 모두 적다보면, 패턴이 보이는 문제이다.
      
    바로 피보나치!!
      
    N=1, [1]
    N=2, [11, 00]
    N=3, [111, 001, 100] 이 가능하다.
      
    1,2,3 까지 보면, 이전 것에 숫자를 붙이는 형식으로 표현이 가능해진다.
    N=3을 기준으로 본다면, N-2인 1일 때 뒤에 00을 붙이는 경우와, 
    N-1인 2일 때 뒤에 1을 붙이면 N=3인 경우와 경우의 수가 맞는다.
      
    혹시 모르니 5까지 이어서 보면...
      
    N=4, [1111, 0011, 1001, 1100, 0000]
    N=5, [11111, 00111, 10011, 11001, 00001, 11100, 00100, 10000]
      
    으로 각각 N-2에 00을 붙이는 경우 + N-1에 1을 붙이는 경우가 현재 N의 경우의 수임을
    알 수 있다.
      
    여기서 N을 15746로 나누는 것도 잊지 말고 해야한다.(이것 때문에 많이 틀렸다.)
  

• 답안

    if __name__ == "__main__":
        N = int(input())
        a1 = 1
        a2 = 2
        if N < 3:
            print(N)
        else:
            before = ()
            for i in range(3, N + 1):
                if i == 3:
                    before = (a1, a2)
                else:
                    before = (before[1], (before[0] + before[1]) % 15746)
            print((before[0] + before[1]) % 15746)