[백준]1904번 01타일 - DP

 

n = int(input())

dp = [1, 2, 3]
if n <= 3:
    print(int(dp[n-1]))
else:
    for i in range(3, n):
        dp.append((dp[i - 2] + dp[i - 1]) % 15746) # 1,000,000이 들어올 경우 값이 int 범위를 벗어날 수 있음
        # 따라서 애초에 나머지 연산을 수행 후 값을 저장.
    print(int(dp[-1]))

 

코드 설명

처음에 길이가 1, 2, 3 으로 만들 수 있는 갯수를 지정하여 초기화 하여 준다. 만약 3 미만일 경우에는 저장된 값에서 바로 출력한다.

그렇지 않을 경우에는 3부터 반복을 통해 dp[i-2] + dp[i-1] 점화식을 이용하여 값을 누적시켜 준다.

저장된 값중 가장 마지막에 있는 값을 출력하여 준다.

 

Point : DP 문제는 점화식을 세우는 것이 중요하다. 초기 갯수는 3개로 진행하였고, 4개 이상 진행될 시에는 i-2 번째와 i-1 번째의 값을 더한 식이 나오게 된다. 추가적으로 숫자의 범위가 크므로 값을 저장할 때 미리 %15746 나머지 연산을 수행해서 int 값의 범위를 벗어나는 것을 방지해 줄 수 있다. (마지막에 나머지 연산하는 것과 결과는 동일하게 나온다)