백준 11726 문제 풀이 python

🐒 2×n 타일링

https://www.acmicpc.net/problem/11726

✍ 나의 풀이

n = int(input())

dp = [0] * (n+1)

if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    dp[1] = 1
    dp[2] = 2

    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]

    print(dp[n]%10007)

첫트에 못풀고 구글링 해서 이해를 했고, 나중에 다시 풀었다.
나중에 풀때는 16분 가량 걸렸다.

🧠 문제 이해

문제에서 제시하는 경우의 수를 한번 나열해보고 규칙을 이해하는게 중요한 것 같다.

가로크기가 1일때 서있는 블럭 한개만 올 수 있다.

가로크기가 2일때 서있는 블럭 두개 또는 누워있는 블럭 두개가 올 수 있다.

가로크기가 3일때 서있는 블럭 세개, 누워있는 블럭 두개 에 서있는 블럭 한개가 오른쪽 왼쪽에 붙는 방법이 있다.

가로크키가 4일때를 관찰해보면

• 가로크기가 3일때 발생하는 방법의 수에 서있는 블럭 한개가 오른쪽에 붙는 모양 과
• 가로크기가 2일때 발생하는 방법의 수에 누워있는 블럭 두개가 오른쪽에 붙는 모양이 나타남을 볼 수 있다.

가로크기가 3일때 방법의 수와 가로크기가 2일때의 방법의 수의 합이 가로크기 4일때의 방법의 수가 된다.

가로크기 5일때 또한 가로크기 5-1 방법의 수 와 가로크기 5-2 방법의 수의 합으로 나타남을 볼 수 있다.

따라서 현재 확인 하고있는 가로크기 i의 방법의 수가 dp[i] 일때의 점화식은

피보나치 수열에서 나타나는 점화식과 똑같다.

💡 코드

n = int(input())

dp = [0] * (n+1)
 #0부터 n까지의 가로크기의 방법의 수를 저장할 수 있는 리스트
 
if n == 1:
    print(1)
     #가로크기가 1일때 1출력
elif n == 2:
    print(2)
     #가로크기가 2일때 2출력

else:	 #가로크기가 1또는 2가 아니면
    dp[1] = 1	
    dp[2] = 2 
    	#dp 테이블에 가로크기가 1, 2일때 방법의 수 저장
        
    for i in range(3,n+1):	#가로크기가 3부터일떄 n까지 반복
        dp[i] = dp[i-1] + dp[i-2]

    print(dp[n]%10007)

🔍 다른 답안

if문으로 가로크기가 1,2일때를 따로 처리하는게 지저분해보이면
dp테이블의 크기를 하드코딩하면 된다.
문제에서는 가로크기가 최대 1000까지 발생할 수 있으므로
0부터 1000까지의 가로크기의 방법의 수를 저장하는 리스트를 만들면 된다.

n = int(input())

dp = [0] * (1001)

dp[1] = 1
dp[2] = 2

for i in range(3,n+1):
    dp[i] = dp[i-1]+dp[i-2]

print(dp[n]%10007)

그러나 하드코딩을 할 때 문제점은 문제에서 제시하는 n의 최대값이 커질수록 메모리 사용량이 늘어날 것이다.

후기

잘 풀리면 재밌는데..