์ ๋ ฅ
์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. N์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ ๋ต์ 1,000,000,000์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค.
ํด๊ฒฐ ๋ฐฉ๋ฒ
์ฐ์ ๊ท์น์ ์ฐพ์ ํ์๊ฐ ์๋ค.
๊ธธ์ด๊ฐ 1์ธ ๊ณ๋จ์ ์๋ ๋ช ๊ฐ๊ฐ ์์๊น?
1 2 3 4 5 6 7 8 9
๋ต์ 9๊ฐ
๊ทธ๋ผ ๊ธธ์ด๊ฐ 2์ธ ๊ณ๋จ์ ์๋?
10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98
๋ต์ 17๊ฐ
๊ท์น์ด ๋ณด์ด๋๊ฐ? ๋ณด์ด์ง ์์๋ ๋๋ค.
(๋ณธ์ธ๋ ํธ๋๋ฐ ์ค๋๊ฑธ๋ ธ์ผ๋... ์ด ๋ฌธ์ ๋ง์ด ์ด๋ ค์ ์๋ค. ์ ํ์์ ์ ๋ํ ๊ท์น์ ์ฐพ์ง ๋ชปํ๊ธฐ ๋๋ฌธ์ด์๋ค...)
๋ณด๊ธฐ ์ฝ๊ฒ ๋ํ๋ด๊ธฐ ์ํด ํ๋ก ์ค๋ช ํ๊ฒ ๋ค.
index๋ก ๋๋๋ ์๋ฅผ ์ ์ฅํ dp๋ฅผ ๋ง๋ค์ด ์ค๋ค.
โ dp[0][0]์ 0์ผ๋ก ๋๋๋ 1์๋ฆฌ ์, dp[0][9]๋ 9๋ก ๋๋๋ 1์๋ฆฌ ์๊ฐ ์ ์ฅ๋๋ค.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
๊ธธ์ด 1 : 0 (0์ ๊ธธ์ด 1์ ํฌํจ๋์ง ์์ง๋ง dp๋ฅผ ํํํ๊ธฐ ์ํด ์์ ) / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9
โก dp[1][0]์ 0์ผ๋ก ๋๋๋ 2์๋ฆฌ ์, dp[1][9]๋ 9๋ก ๋๋๋ 2์๋ฆฌ ์๊ฐ ์ ์ฅ๋๋ค.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
๊ธธ์ด 2 : 10 / 21 / 12 32 / 23 43 / 34 54 / 45 65 / 56 76 / 67 87 / 78 98 / 89
โข dp[2][0]์ 0์ผ๋ก ๋๋๋ 3์๋ฆฌ ์, dp[2][9]๋ 9๋ก ๋๋๋ 3์๋ฆฌ ์๊ฐ ์ ์ฅ๋๋ค.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
๊ธธ์ด 3 : 210 / 101 121 321 / 212 232 432 / ... / 678 878 878 / 789 989
๊ท์น์ด ๋ณด์ด์ง ์๋๊ฐ?
i์ j ๊ฐ์ ๊ฒฝ์ฐ i-1์ j-1๊ณผ j+1์ด ์ฌ์ฉ๋๋ ๊ฒ์ ๋ณผ ์ ์๋ค.
์๋ฅผ ๋ค์ด i[2][8]์ด๋ฉด 8๋ก ๋๋๋ 3์๋ฆฌ ์์ธ๋ฐ i[1][7]์ 67, 87 ๊ณผ i[1][9]์ 89 ๋ค์ 8์ด ๋ถ์ด์
678, 878, 898์ด ๋๋ ๊ฒ์ ๋ณผ ์ ์๋ค.
๋ฐ๋ผ์ ์ ํ์์ dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] ์ด๋ค.
ํ์ง๋ง dp[i][0]๊ณผ dp[i][9]์ธ ๊ฒฝ์ฐ๋ฅผ ์ฃผ์๊น๊ฒ ์ดํด๋ณผ ํ์๊ฐ ์๋ค.
์์ ์ ํ์์ ๋์ผํ๊ฒ ์ ์ฉํ๋ฉด ๋ฐฐ์ด์ index๋ฅผ ๋์ด๊ฐ๊ธฐ ๋๋ฌธ์ ์ค๋ฅ๊ฐ ๋ฐ์ํ๋ค.
์ฆ, ํด๋น ๊ฒฝ์ฐ์๋ ๋ค๋ฅธ ์ ํ์์ด ์ ์ฉ๋๋ ๊ฒ์ ์๊ฐํ ์ ์๋๋ฐ ๊ท์น์ ์ฐพ์๋ณด๋ฉด
dp[i][0]์ ๊ฒฝ์ฐ dp[i-1][1], dp[i][9]์ ๊ฒฝ์ฐ dp[i-1][8]๊ณผ ๊ฐ๋ค๋ ๊ฒ์ ๋ณผ ์ ์๋ค.
๋ฐ๋ผ์ ์ต์ข ์ ์ธ ์ ํ์์
dp[i][j] = dp[i-1][j+1] ( j == 0 )
dp[i-1][j-1] + dp[i-1][j+1] ( 1 ≤ j ≤ 8 )
dp[i-1][j-1] ( j == 9 )
๊ฐ ๋๋ค.
ํด๊ฒฐ ๊ณผ์
์์ ์ ํ์์ผ๋ก ์ฝ๋๋ฅผ ์์ฑํ๊ณ ๋ฌธ์ ์์ 10์ต์ผ๋ก ๋๋ ์ค ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ผ๊ณ ํ์ผ๋ฏ๋ก 10์ต์ผ๋ก ๋๋ ์ค๋ค.
์ต์ข ์ ์ธ ์ฝ๋๋
'โ๏ธ ์ฝํ ์ค๋น > Dynamic Programming' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋์ ๊ณํ๋ฒ 1] [C++] 11053๋ฒ. ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด (0) | 2021.01.25 |
---|---|
[๋์ ๊ณํ๋ฒ 1] [C++] 2156๋ฒ. ํฌ๋์ฃผ ์์ (0) | 2021.01.25 |
[๋์ ๊ณํ๋ฒ 1] [C++] 1463๋ฒ. 1๋ก ๋ง๋ค๊ธฐ (0) | 2021.01.19 |
[๋์ ๊ณํ๋ฒ 1] [C++] 2579๋ฒ. ๊ณ๋จ ์ค๋ฅด๊ธฐ (0) | 2021.01.14 |
[๋์ ๊ณํ๋ฒ 1] [C++] 1932๋ฒ. ์ ์ ์ผ๊ฐํ (0) | 2021.01.13 |