백준 다이나믹 프로그래밍 11726번

안녕하세요 GDSC ML 멤버 나건주입니다.
파이썬 알고리즘 스터디 8번째 주제 다이나믹 프로그래밍의 6번째 문제를 풀어보았습니다.
다이나믹 프로그래밍의 뜻부터 알아보겠습니다.

다이나믹 프로그래밍

다이나믹 프로그래밍은 동적 계획법이라고도 부르며 큰 문제를 작은 문제로 나누어 푸는 문제입니다.
다음과 같은 문제에서 다이나믹 프로그래밍을 사용합니다.

최적 부분 구조 (Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다.

중복되는 부분 문제 (Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결해야 합니다.

메모이제이션 (Memoization)

메모이제이션은 한 번 계산한 결과를 메모리 공간에 메모(캐싱)하는 기법입니다.
같은 문제를 다시 호출하면 메모한 결과값을 가져옵니다.

탑다운과 보텀업

탑다운은 하향식, 보텀업은 하향식 방법입니다.
메모이제이션은 탑다운 방식에서 사용됩니다.
결과 저장용 리스트는 DP 테이블이라고 합니다.

11726번 2×n 타일링

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

문제는 2Xn 타일을 1X2와 2X1 타일로 채우는 방법의 수를 구하는 문제입니다.

DP 문제이기 때문에 아마도 점화식을 이용한 풀이가 더 적절할 것 같습니다.

점화식을 통한 풀이

n=3일 때, 경우의 수는 n=1일 때 + n=2일 때와 같습니다.

즉, 길이가 n인 경우 n-1일 때 뒤에 1X2 하나를 더 붙이거나, n-2일 때 2X1 두 개를 더 붙이는 경우의 합이 n일 때 경우의 수가 됩니다.
따라서 dp를 만들어서 결과값들을 순서대로 저장하고 n-1번째와 n-2번째의 합을 계속 구해준다면 n번째의 합이 나오게 됩니다.

n = int(input())

dp = [0 for i in range(x+1)]

if n < 3: # 3미만에서의 결과는 x 그대로 입니다.
    print(n)
else:
    dp[1] = 1 # 점화식을 위한 첫번째 두번째 값
    dp[2] = 2
    for i in range(3, n+1): # 점화식 시작
        dp[j] = dp[j-1] + dp[j-2]

    print(dp[n] % 10007)

9
55

팩토리얼을 통한 풀이

2X1 타일은 홀수개를 이용할 수는 없으므로 가로 길이/2의 몫이 최대 2X1 타일의 개수일 것입니다.
1X2 타일은 전체 길이에서 2X!타일의 개수를 뺀 값이 됩니다.
따라서 모든 경우를 반복문으로 돌려서 리스트에 저장할 수 있습니다.

예전 순열과 조합 부분을 기억해보면 물건 a,b가 각각 n개, m개 있을 때 경우의 수는 (n+m)!/(n!*m!)입니다.
따라서 팩토리얼을 구해주는 방식만 안다면 쉽게 해결할 수 있습니다.
파이썬에서 팩토리얼을 구하는 방식에 반복문, 재귀, math library가 있습니다.

한가지 주의할 점은 (n+m)!/(n!m!)를 (n+m)!//(n!m!)로 바꿔주지 않으면 실수와 정수가 달라서 답이 틀립니다.
또한 재귀 함수를 이용한다면 RecrusionError가 발생할 수 있으므로 sys.setrecursionlimit()을 통해 재귀 깊이를 제한할 수 있습니다.

n=int(input()) #직사각형의 가로 길이

a=1 # 1X2 타일 사용
b=2 # 2X1 타일 사용 -> 하나만 사용할 수는 없으므로 2개를 한 묶음으로 생각한다.  

dp=[]

for num_b in range((n//2)+1): #이용 가능한 2X1 타일의 개수
    num_a=n-num_b*2 #이용 가능한 1X2 타일의 개수
    dp.append((num_a,num_b)) # 두 타일로 만들 수 있는 조합의 개수

result=0

while len(dp)!=0: # 경우의 수가 없을 때까지
    n_a,n_b=dp.pop() # 각 경우의 수 pop
    fact_total=1 #factorial은 1부터 시작
    for i in range(1,n_a+n_b+1): # 분자 factorial
        fact_total*=i
    fact_a=1
    fact_b=1
    for i in range(1,n_a+1): # 분모 factorial
        fact_a*=i
    for i in range(1,n_b+1):
        fact_b*=i
    result=result+(fact_total//(fact_a*fact_b))
    
print(int(result)%10007)

9
55

모두 과제랑 팀플이랑 기말까지 화이팅입니다!!!!!

알고리즘 다이나믹 프로그래밍-11726번

다이나믹 프로그래밍 11726번 풀이