중복조합1 백준 2688 자바 - 줄어들지 않아 (BOJ 2688 JAVA) 문제 : boj2688 방법 1. dp로 풀기 dp[a][b]를 a개의 수를 가지고 표현할 때 마지막 수가 b일 경우의 수 라고 정의하자. 그럼 이 문제에 대한 dp 점화식은 다음과 같다. 즉, 개수가 하나 더 작은 경우에서(dp[a-1]), 자신보다 작은 경우들에다가 자기 자신을 붙여주면 된다. 예를들어서 현재 b가 3일 경우 001과 113뒤에 3을 붙여 0013, 1133을 만들면 조건을 만족한다. 이 점화실을 a는 1부터 입력받은 n까지, b는 0부터 9까지 진행하면 된다. 그리고 여기에 prefix sum 까지 살짝 넣어주면 시그마를 없애서 시간 복잡도를 좀 더 간소화 시킬 수 있다. 거기에 미리 최대치인 a=64까지 계산해두고, 각 T개의 n개마다 dp[n][0]+dp[n][1]+...+dp[.. 2022. 2. 3. 이전 1 다음
