Joonas' Note

BOJ 2225 - 합분해 본문

알고리즘/문제 풀이

BOJ 2225 - 합분해

joonas 2018.04.24 17:06

링크: 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 - 감시  (0) 2018.05.17
BOJ 1525 - 퍼즐  (0) 2018.05.08
BOJ 2225 - 합분해  (0) 2018.04.24
BOJ 3075 - Astromeeting  (0) 2018.04.18
BOJ 15656 - 치킨 배달  (0) 2018.04.17
BOJ 15685 - 드래곤 커브  (0) 2018.04.17
0 Comments
댓글쓰기 폼