[백준] 1010번 다리 놓기

 

 

 

 

이 문제는 2가지 풀이법으로 해결했습니다.

1. 조합

2. DP

 

1. 조합

문제를 봤을 때 가장 직관적으로 생각났습니다. 

# 조합으로 풀기
def fac(a):
    num = 1
    for i in range(1,a+1):
        num *= i
    return num

t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    
    res = fac(m)//(fac(n)*fac(m-n))
    print(res)

 

 

2. DP

DP 문제를 풀어보려고 DP 문제 목록에서 골랐기 때문에 DP인걸 알 수 있었습니다. 하지만 문제만 보고 DP라는걸 알아차리는 것이 쉽지 않은 것 같습니다..ㅎㅎ

 

 

위 그림처럼 경우의 수가 규칙성을 가졌습니다. 그래서 작은문제로 쪼개어 해결할 수 있었습니다.

# DP로 풀기
dp = [[0]*30 for _ in range(30)]
t = int(input())

for i in range(30):
    for j in range(30):
        if i == 1:
            dp[i][j] = j
        else:
            if i == j :
                dp[i][j] = 1
            elif i < j :
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
                
for _ in range(t):
    n,m = map(int,input().split())
    print(dp[n][m])

 

 

 

아직 DP로 사고하는 것이 어려운 것 같습니다.

좀 더 많은 문제를 접해봐야할 것 같습니다!