본문 바로가기

22251

[BOJ] 2225 : 합분해 문제 링크 2225번: 합분해 (acmicpc.net) 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP를 이용해서 숫자 N을 K개의 숫자 조합으로 만드는 경우의 수를 출력하는 문제. 풀이 DP[N][K] 배열을 만들어서 DP[Y][X] 에는 숫자 Y를 숫자 X개를 조합해서 만드는 경우의 수를 저장해야겠구나 생각했다. 일단 Bottom-up 방식으로 DP[0][1], DP[1][1], ... , DP[N][1], DP[0][2], DP[1][2], ... , DP[N][K] 이렇게 채워나가야겠다고 생각은 했지만, 점화식을 어떻게 해야할 지가 관건이다. 처음에는 예를 들어 DP[3][3]을 채우기 위해서는 DP[0][1] * DP[3.. 2022. 3. 2.

이전 1 다음

티스토리툴바