2225번: 합분해
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
dfs 문제인 줄 알았는데.. DP 문제다.
잘 모르겠어서 이삭님 풀이 보고 풀었다.
blog.naver.com/kdy246/222184773335
백준 알고리즘 - #2225 합분해 문제/생각 정리
문제문제 풀이한 방법이 문제는 다이나믹 프로그래밍을 활용하면 쉽게 풀 수 있었다.생각해봐야 할 것은 ...
blog.naver.com
파스칼의 삼각형 문제로 D[i-1][j] + D[i][j-1]을 반복해서 계산하는 형태이다.
그런데.. 왜 D[N][K] 가 답이 아닌 D[N][K-1] 이 답이 되는지는 모르겠다.. 움움
어렵네