Joonas' Note

Joonas' Note

BOJ 2225 - 합분해 본문

알고리즘/문제 풀이

BOJ 2225 - 합분해

2018. 4. 24. 17:06 joonas

    링크: https://www.acmicpc.net/problem/2225


    문제의 예시로 n=20, k=2일 때 나올 수 있는 경우의 수는

     0 + 20

     1 + 19

     2 + 18

       ...

    19 + 1

    20 + 0

    로 총 21개이다.


    풀이

    n=20이고 k=3이라면, 경우의 수는 아래와 같은 모양으로 전개된다.

    (n=20, k=3) =

       (n=20, k=2)

    + (n=19, k=2)

    + ...

    + (n=1, k=2)

    + (n=0, k=2)


    3개의 수를 n=20 내에서 고르는 경우의 수 = 

       첫 번째 수로 0을 사용하고, 나머지 2개의 수를 n=20 내에서 고르는 경우의 수

    + 첫 번째 수로 1을 사용하고, 나머지 2개의 수를 n=19 내에서 고르는 경우의 수

    + ....


    작은 문제로 쪼개어 해결이 가능하다. dp 테이블을 두고 메모이제이션했다.


    k=1이면 가능한 경우는 n을 선택하는 1가지 밖에 없으므로 f(n, 1) = 1 이다.


    코드



    '알고리즘 > 문제 풀이' 카테고리의 다른 글

    BOJ 15683 - 감시  (2) 2018.05.17
    BOJ 1525 - 퍼즐  (0) 2018.05.08
    BOJ 3075 - Astromeeting  (0) 2018.04.18
    BOJ 15656 - 치킨 배달  (0) 2018.04.17
    BOJ 15685 - 드래곤 커브  (0) 2018.04.17
    Comments