[BOJ] 11726번 2xn 타일링 / 사용언어 : 파이썬(python)

※ 문제링크

11726번: 2×n 타일링

해당 문제는 메모이제이션 개념과 피보나치 수열의 개념을 이해하면 풀 수 있는 문제였다. 점화식 도출을 위해 간단하게 n = 1부터 n = 5까지 결과값을 생각해봤다. 각각의 n의 값이 1, 2, 3, 4, 5일때 결과값은 1, 2, 3, 5, 8이 도출되는 것을 확인하였고, n이3이상일때부터는 f(n) = f(n-1) + f(n-2)인것을 추론하여 문제에 대입해보았더니 해결이 되었다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력값을 바탕으로 메모이제이션을 적용하여 결과값을 작성할 dp리스트를 작성한다.

2. 값이 들어오면 반복문을 통해 바텀업 방식으로 결과값을 구하고 출력한다.

 

# n = 1 : 1개 / n = 2 : 2개 / n = 3 : 3개 / n = 4 : 5개
N = int(input())
if N > 3:
    dp = [0 for _ in range(N+1)]
else:
    dp = [0 for _ in range(4)]
dp[1] = 1
dp[2] = 2
dp[3] = 3
for i in range(4, N+1):
    dp[i] = (dp[i-1] + dp[i-2]) % 10007
print(dp[N])

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.