합분해 썸네일형 리스트형 [백준][Python][2225][DP] 합분해 문제 : https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제다. 배열의 의미는 다음과 같다 세로 K = K개의 숫자를 쓴다 가로 N = 0-n 까지를 써서 만든다. 이랬을 때, 문제 조건상 1개의 숫자로 만들수 있는 n 후보들의 갯수는 1이다. 0을 0번써서 만드는 건 1로 하자. 이때, i개를 써서 j를 만드는 방법의 갯수는 (i-1개를 써서 0-j 까지를 만드는 방법의 갯수의 총 합) 으로 나타낼 수 있다. 왜냐면, 10 = 9를 만드는 방법의 수 + 1, 8을 만드는 방법의 수 +2 ... 이런 식으로 나타낼 수 있기 때문이다. 원래는 10을 만드는 방법의 .. 더보기 이전 1 다음
