๋ชฉ๋กํ•ฉ๋ถ„ํ•ด (1)

Hello Ocean! ๐ŸŒผ

[๋ฐฑ์ค€/C++] 2225. ํ•ฉ๋ถ„ํ•ด

๋ฌธ์ œ www.acmicpc.net/problem/2225 2225๋ฒˆ: ํ•ฉ๋ถ„ํ•ด ์ฒซ์งธ ์ค„์— ๋‹ต์„ 1,000,000,000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net ์œ ์˜์‚ฌํ•ญ 1+2 ์™€ 2+1์„ ๋‹ค๋ฅธ ๊ฒฝ์šฐ๋กœ ์„ผ๋‹ค๋Š” ๊ฒƒ. 0๋„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ. ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ 1000000000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•ด์•ผํ•œ๋‹ค๋Š” ๊ฒƒ ํ’€์ด ์ด ๋ฌธ์ œ๋Š” DP(๋™์  ๊ณ„ํš๋ฒ•)์„ ์ด์šฉํ•˜๋ฉด ํ’€ ์ˆ˜ ์žˆ๋‹ค! 2์ฐจ์› ์บ์‹œ๋ฐฐ์—ด์„ ์ด์šฉํ•œ ๋ฉ”๋ชจ์ด์ œ์ด์…˜์„ ์ ์šฉํ•ด์•ผ ํ•œ๋‹ค. cache[k][n] : k๊ฐœ์˜ ์ˆซ์ž๋ฅผ ๋”ํ•ด์„œ n์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜ ๊ทธ๋ฆฌ๊ณ  cache[k][n]์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค. (์ ํ™”์‹) cache[k][n] = cache[k-1][0] + cache[k-1][1] + cacke[k-1][2] + ... + c..
Algorithm 2021. 3. 24. 14:22
์ด์ „ Prev 1 Next ๋‹ค์Œ