728x90
반응형
※ 문제링크
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
해당 문제는 메모이제이션 개념과 피보나치 수열의 개념을 이해하면 풀 수 있는 문제였다. 점화식 도출을 위해 간단하게 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 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 2644번 촌수계산 / 사용언어 : 파이썬(python) (0) | 2022.02.08 |
---|---|
[BOJ] 11057번 오르막수 / 사용언어 : 파이썬(python) (0) | 2022.02.07 |
[BOJ] 10282번 해킹 / 사용언어 : 파이썬(python) (0) | 2022.01.30 |
[BOJ] 1854번 K번째 최단경로 찾기 / 사용언어 : 파이썬(python) (0) | 2022.01.30 |
[BOJ] 2665번 미로만들기 / 사용언어 : 파이썬(python) (0) | 2022.01.30 |
댓글