๋ฌธ์
์ค๋ฅด๋ง ์๋ ์์ ์๋ฆฌ๊ฐ ์ค๋ฆ์ฐจ์์ ์ด๋ฃจ๋ ์๋ฅผ ๋งํ๋ค. ์ด๋, ์ธ์ ํ ์๊ฐ ๊ฐ์๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์น๋ค.
์๋ฅผ ๋ค์ด, 2234์ 3678, 11119๋ ์ค๋ฅด๋ง ์์ด์ง๋ง, 2232, 3676, 91111์ ์ค๋ฅด๋ง ์๊ฐ ์๋๋ค.
์์ ๊ธธ์ด N์ด ์ฃผ์ด์ก์ ๋, ์ค๋ฅด๋ง ์์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ 0์ผ๋ก ์์ํ ์ ์๋ค.
## ์ ๋ ฅ
์ฒซ์งธ ์ค์ N (1 โค N โค 1,000)์ด ์ฃผ์ด์ง๋ค.
## ์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๊ธธ์ด๊ฐ N์ธ ์ค๋ฅด๋ง ์์ ๊ฐ์๋ฅผ 10,007๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค.
์๊ฐ ์ ํ | ๋ฉ๋ชจ๋ฆฌ ์ ํ | ์ ์ถ | ์ ๋ต | ๋งํ ์ฌ๋ | ์ ๋ต ๋น์จ |
---|---|---|---|---|---|
1 ์ด | 256 MB | 51093 | 25041 | 19405 | 47.786% |
https://www.acmicpc.net/problem/11057
ํ์ด
์๊ณ ๋ฆฌ์ฆ ํ๋ฆ
์๋ฆฌ์ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
3 | 55 | 45 | ... | ... | ... |
ํ๋ฅผ ๋ณด๋ฉด ์ธ๋ก๋ ์๋ฆฌ์ N์ด๊ณ , ๊ฐ๋ก๋ 0~9๊น์ง์ ์ซ์์ด๋ค.
์ฑ์์ง๊ฐ์ dp[n][i]
n: ์๋ฆฌ์ , i:์ ์ผ ๋ท์๋ฆฌ ์ซ์ ๋ฅผ ํตํด i๋ฅผ ๊ฐ์ง๊ณ N์๋ฆฌ์๋ฅผ ๋ง๋ค์์๋์ ๊ฐฏ์์ด๋ค.
n=1์ผ๋ 0,1,2,3,4,5,6,7,8,9 ๊ฐ ๊ฐ๋ฅํ๊ณ ,
n=2์ผ๋
i=0 ์ด๋ฉด 00 01 02 03 04 05 06 07 ...
i=1 ์ด๋ฉด 11 12 13 ...
์์ผ๋ก ๊ตฌํ ์์๊ณ
๋ง์ง๋ง์ธ 9๋ก๋ 99๋ฅผ ๋ง๋ค์์๋ค.
์ฆ ๊ท์น์ ์ฐพ์๋ณด๋ฉด, N์๋ฆฌ์์ i ๋ฒ๊ฐ์ n-1
์๋ฆฌ์์ i ~ 9
๊น์ง์ ๊ฐ์ ๋ชจ๋ ๋ํ๊ฐ์ด๋ค.
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 10; j++) {
for (int k = j; k < 10; k++) {
dp[i][j] += dp[i - 1][k];
dp[i][j] %= MOD;
}
}
}
์ฝ๋
package ๊ธฐ์ด1.Day20.์ ํด์;
import java.util.Arrays;
import java.util.Scanner;
public class ์ค๋ฅด๋ง์ {
static int MOD = 10007;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//์ด์ ์๋ฆฌ๋ง ๊ณ ๋ คํ๋ฉด ๋๋ค.
int n = sc.nextInt(); //์๋ฆฌ
int[][] dp = new int[n + 1][10];//n:์๋ฆฌ์ 10:๋ง์ง๋ง์
Arrays.fill(dp[1], 1);
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 10; j++) {
for (int k = j; k < 10; k++) {
dp[i][j] += dp[i - 1][k];
dp[i][j] %= MOD;
}
}
}
System.out.println(Arrays.stream(dp[n]).sum()%MOD);
sc.close();
}
}
DP์ 3์ค for๋ฌธ์ ์ฌ์ฉํ๋ ๊ฒฝ์ฐ๋ ์ฒ์์ด์ฌ์ ๊ตฌํ์ด ํ๋ค์๋ค. ์ฌ์ด๋ฌธ์ ์ด๊ณ ๋ถ๋ช ์ ๊ทผ๊น์ง ํ๋๋ฐ 3์ค for๋ฌธ์ ์ฌ์ฉํด๋ ๋๋์ง ์๊ฐ์ด ๋ง์์ก์๋ค. ๊ทธ๋ฆฌ๊ณ
System.out.println(Arrays.stream(dp[n]).sum()%MOD);
์ด๋ ๊ฒ ๋ง์ง๋ง์ MOD ์ฐ์ฐ์ ์ํด์ 2๋ฒ์ ๋ ๋ ์๋ฌ๊ฐ ๋ฐ์ํ๋ค. ์์ชฝ์์๋ง ํด์ฃผ๋๊ฒ ์๋๋ผ ์ค์ ๋์ค๋๊ฐ์์๋ MOD๋ฅผ ํด์ฃผ์.