[백준/Python] 1904 01타일

[백준/Python] 1904 01타일

정답 코드 및 설명

전체 코드

def count_binary_sequences(N):
    # 초기 조건 설정
    dp = [0] * (N+1)
    dp[1] = 1
    if N >= 2:
        dp[2] = 2

    # 점화식에 따라 dp 배열 채우기
    for i in range(3, N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % 15746

    # 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지 반환
    return dp[N]

N = int(input())
print(count_binary_sequences(N))

이 문제는 다이나믹 프로그래밍, DP 기법을 활용하여 해결할 수 있는 문제이다. 문제의 핵심은 길이가 N인 2진 수열을 만드는 데 있어서, 마지막이 '00' , '1' 로 끝나는 경우를 어떻게 처리하느냐에 있다. 이 문제에서 가능한 타일의 종류는 '1' 과 '00' 이므로 어떤 길이 N의 수열을 만들 때 마지막에 '1' 을 추가하거나 마지막 두 자리에 '00' 을 추가하는 방법이 있다.

DP 배열 'dp[n]' 을 정의하여 'dp[i]' 는 길이가 'i' 인 모든 2진 수열의 개수를 저장한다.

• 초기 조건 'dp[1] = 1' , 'dp[2] = 2' (길이가 1일 때 '1' 하나만 가능하고, 길이가 2일때는 '00', '01' 두 가지 가능하다.

• 점화식
  dp[i] = (dp[i-1] + dp[i-2]) % 15746

여기서 dp[i-1] 은 마지막에 '1' 타일을 추가하는 경우의 수를 나타내고, dp[i-2] 는 마지막에 '00' 타일을 추가하는 경우의 수를 나타낸다. 길이가 i-1 인 수열 끝에 '1' 을 추가하거나 i-2 인 수열 끝네 '00' 을 추가하여 길이가 i 인 수열을 만들 수 있기 때문이다. 주어진 문제의 요구사항에 따라서 모든 연산 후 결과값을 15746 으로 나눈 나머지를 구해준다.