[1010] 다리 놓기

  • node.js: [:o:]
    • 20200415
    • 01:51:04 .32 +α
    • 시도: 10번
  • C: [:o:]
    • 20200415
    • -
    • 시도: 6번

메모

  • DP문제 & 조합 문제!
  • 조합으로 풀 경우,
    • DP로 풀 경우, 너무 오래 걸린다.. (code2)
    • mCn 을 계산하면 그냥 답이 나온다.. (code1)
  • DP로 풀 경우
    • 탐색을 통해 M의 마지막 노드에 도달할 수 있는 경우의 수를 구한다
    • 단, 이렇게 구하게 되면.. 시간 초과가 뜨게 된다..(C, JS 공통) (code2)
    • 이 글처럼, 미리 모든 값을 구한 후, n과 m값에 맞추어 계산하면 시간초과를 피할 수 있다! (code3)
    • // path[n][m]
[ 1,    1,    1, 1, 1,     1,     1,  1,  1, null, null ...
[ 0, (*)1,    2, 3, 4,     5,     6,  7,  8,    9, null ...
[ 0, (*)0, (*)1, 3, 6,    10,    15, 21, 28,   36,   45 ...
[ 0,    0,    0, 1, 4, (*)10,    20, 35, 56,   84,  120 ...
[ 0,    0,    0, 0, 1, (*) 5, (*)15, 35, 70,  126,  210 ...
[ 0,    0,    0, 0, 0,     1,     6, 21, 56,  126,  252 ...
[ 0,    0,    0, 0, 0,     0,     1,  7, 28,   84,  210 ...
[ 0,    0,    0, 0, 0,     0,     0,  1,  8,   36,  120 ...
      • n==2 부터 path[i][j] = path[i-1][j-1] + path[i][j-1] 이 성립한다!

참고

  • 순열과 조합 개념
    • 순열
      • n개 중 r개를 순서를 고려하여 만들 수 있는 짝의 개수
      • [1,2,3] 중, 2개를 고를 경우,
        • [1,2], [1,3], [2,3], [2,1], [3,1], [3,2]
        • 총 6개
    • 조합
      • n개 중 r개를 순서를 고려하지 않고 만들 수 있는 짝의 개수
      • [1,2,3] 중, 2개를 고를 경우,
        • [1,2], [1,3], [2,3]
        • 총 3개
    • 따라서, 1010번 문제는 조합을 통해 경우의 수를 모두 구할 수 있다는 결론
      • 공식은 구글에 검색해보길..



Link