C++

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[DFS์™€ BFS] [Python / C++] 1260. DFS์™€ BFS

๋ณธ ๊ฒŒ์‹œ๊ธ€์€ PC๋ฒ„์ „์— ์ตœ์ ํ™” ๋˜์–ด์žˆ์Šต๋‹ˆ๋‹ค. www.acmicpc.net/problem/1260 1260๋ฒˆ: DFS์™€ BFS ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 โ‰ค M โ‰ค 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 โ‰ค M โ‰ค 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ์ด์— ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ฐ„์„ ์ด ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ๊ฐ„์„ ์€ ์–‘๋ฐฉํ–ฅ์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— DFS๋ฅผ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Shortest Path

[์ตœ๋‹จ ๊ฒฝ๋กœ] [Python / C++] 1956. ์šด๋™ - GOLD โ…ฃ

๋ณธ ๊ฒŒ์‹œ๊ธ€์€ PC๋ฒ„์ „์— ์ตœ์ ํ™” ๋˜์–ด์žˆ์Šต๋‹ˆ๋‹ค. 1956๋ฒˆ: ์šด๋™ ์ฒซ์งธ ์ค„์— V์™€ E๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (2 โ‰ค V โ‰ค 400, 0 โ‰ค E โ‰ค V(V-1)) ๋‹ค์Œ E๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ๊ฐ ์„ธ ๊ฐœ์˜ ์ •์ˆ˜ a, b, c๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. a๋ฒˆ ๋งˆ์„์—์„œ b๋ฒˆ ๋งˆ์„๋กœ ๊ฐ€๋Š” ๊ฑฐ๋ฆฌ๊ฐ€ c์ธ ๋„๋กœ๊ฐ€ ์žˆ๋‹ค๋Š” ์˜ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— V์™€ E๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (2 โ‰ค V โ‰ค 400, 0 โ‰ค E โ‰ค V(V-1)) ๋‹ค์Œ E๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ๊ฐ ์„ธ ๊ฐœ์˜ ์ •์ˆ˜ a, b, c๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. a๋ฒˆ ๋งˆ์„์—์„œ b๋ฒˆ ๋งˆ์„๋กœ ๊ฐ€๋Š” ๊ฑฐ๋ฆฌ๊ฐ€ c์ธ ๋„๋กœ๊ฐ€ ์žˆ๋‹ค๋Š” ์˜๋ฏธ์ด๋‹ค. (a โ†’ b์ž„์— ์ฃผ์˜) ๊ฑฐ๋ฆฌ๋Š” 10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. (a, b) ์Œ์ด ๊ฐ™์€ ๋„๋กœ๊ฐ€ ์—ฌ๋Ÿฌ ๋ฒˆ ์ฃผ์–ด์ง€์ง€ ์•Š๋Š”๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ตœ์†Œ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[DFS์™€ BFS] [Python / C++] 1707. ์ด๋ถ„ ๊ทธ๋ž˜ํ”„

www.acmicpc.net/problem/1707 1707๋ฒˆ: ์ด๋ถ„ ๊ทธ๋ž˜ํ”„ ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š”๋ฐ, ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ K(2โ‰คKโ‰ค5)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ๊ฐœ์ˆ˜ V(1โ‰คVโ‰ค20,000)์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š”๋ฐ, ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ K(2โ‰คKโ‰ค5)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ๊ฐœ์ˆ˜ V(1โ‰คVโ‰ค20,000)์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ E(1โ‰คEโ‰ค200,000)๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ์ •์ ์—๋Š” 1๋ถ€ํ„ฐ V๊นŒ์ง€ ์ฐจ๋ก€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ™์–ด ์žˆ๋‹ค. ์ด์–ด์„œ ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ E๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/DFS, BFS

[DFS์™€ BFS] [Python / C++] 7562. ๋‚˜์ดํŠธ์˜ ์ด๋™.

www.acmicpc.net/problem/7562 7562๋ฒˆ: ๋‚˜์ดํŠธ์˜ ์ด๋™ ์ฒด์ŠคํŒ ์œ„์— ํ•œ ๋‚˜์ดํŠธ๊ฐ€ ๋†“์—ฌ์ ธ ์žˆ๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ํ•œ ๋ฒˆ์— ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์€ ์•„๋ž˜ ๊ทธ๋ฆผ์— ๋‚˜์™€์žˆ๋‹ค. ๋‚˜์ดํŠธ๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นธ์ด ์ฃผ์–ด์ง„๋‹ค. ๋‚˜์ดํŠธ๋Š” ๋ช‡ ๋ฒˆ ์›€์ง์ด๋ฉด ์ด ์นธ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ์„ธ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ฒซ์งธ ์ค„์—๋Š” ์ฒด์ŠคํŒ์˜ ํ•œ ๋ณ€์˜ ๊ธธ์ด l(4 โ‰ค l โ‰ค 300)์ด ์ฃผ์–ด์ง„๋‹ค. ์ฒด์ŠคํŒ์˜ ํฌ๊ธฐ๋Š” l ร— l์ด๋‹ค. ์ฒด์ŠคํŒ์˜ ๊ฐ ์นธ์€ ๋‘ ์ˆ˜์˜ ์Œ {0, ..., l-1} ร— {0, ..., l-1}๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๋‘˜์งธ ์ค„๊ณผ ์…‹์งธ ์ค„์—๋Š” ๋‚˜์ดํŠธ๊ฐ€ ํ˜„์žฌ ์žˆ๋Š” ์นธ, ๋‚˜์ดํŠธ๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นธ์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ๊ฐ ํ…Œ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 2565๋ฒˆ. ์ „๊นƒ์ค„

www.acmicpc.net/problem/2565 2565๋ฒˆ: ์ „๊นƒ์ค„ ์ฒซ์งธ ์ค„์—๋Š” ๋‘ ์ „๋ด‡๋Œ€ ์‚ฌ์ด์˜ ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๋Š” 100 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ „๊นƒ์ค„์ด A์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜๋Š” ์œ„์น˜์˜ ๋ฒˆํ˜ธ์™€ B์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜๋Š” www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ๋‘ ์ „๋ด‡๋Œ€ ์‚ฌ์ด์˜ ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๋Š” 100 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ „๊นƒ์ค„์ด A์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜๋Š” ์œ„์น˜์˜ ๋ฒˆํ˜ธ์™€ B์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜๋Š” ์œ„์น˜์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฐจ๋ก€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์œ„์น˜์˜ ๋ฒˆํ˜ธ๋Š” 500 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๊ณ , ๊ฐ™์€ ์œ„์น˜์— ๋‘ ๊ฐœ ์ด์ƒ์˜ ์ „๊นƒ์ค„์ด ์—ฐ๊ฒฐ๋  ์ˆ˜ ์—†๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ๋‚จ์•„์žˆ๋Š” ๋ชจ๋“  ์ „๊นƒ์ค„์ด ์„œ๋กœ ๊ต์ฐจํ•˜์ง€ ์•Š๊ฒŒ ํ•˜๊ธฐ ์œ„ํ•ด ์—†์• ์•ผ ํ•˜๋Š” ์ „๊นƒ์ค„์˜ ์ตœ์†Œ ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 11054๋ฒˆ. ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด

www.acmicpc.net/problem/11054 11054๋ฒˆ: ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ํฌ๊ธฐ N์ด ์ฃผ์–ด์ง€๊ณ , ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด A๋ฅผ ์ด๋ฃจ๊ณ  ์žˆ๋Š” Ai๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N โ‰ค 1,000, 1 โ‰ค Ai โ‰ค 1,000) www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ํฌ๊ธฐ N์ด ์ฃผ์–ด์ง€๊ณ , ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด A๋ฅผ ์ด๋ฃจ๊ณ  ์žˆ๋Š” Ai๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N โ‰ค 1,000, 1 โ‰ค Ai โ‰ค 1,000) ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ๋ถ€๋ถ„ ์ˆ˜์—ด ์ค‘์—์„œ ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ์ˆ˜์—ด์˜ ๊ธธ์ด๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์ด์ „ ๋ฌธ์ œ์ธ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๋ณ€ํ˜• ๋ฌธ์ œ์ด๋‹ค. (์•„์ง ํ’€์ง€ ์•Š์•˜๋‹ค๋ฉด ์•„๋ž˜ ๋ฌธ์ œ๋ฅผ ๋จผ์ € ํ’€์–ด๋ณด๋„๋ก ํ•˜์ž.) www.acmicpc.net/problem/11053 11..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 11053๋ฒˆ. ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด

www.acmicpc.net/problem/11053 11053๋ฒˆ: ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด ์ˆ˜์—ด A๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ˆ˜์—ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์šฐ์— ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์€ A = {10, 20, 10, 30, 20, 50} ์ด www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ํฌ๊ธฐ N (1 โ‰ค N โ‰ค 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด A๋ฅผ ์ด๋ฃจ๊ณ  ์žˆ๋Š” Ai๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค Ai โ‰ค 1,000) ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• a[i]๋ฅผ ์ž…๋ ฅ๋œ ์ˆ˜์—ด, dp[i]๋ฅผ i๋ฒˆ์งธ๊นŒ์ง€ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด๋ผ๊ณ  ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 2156๋ฒˆ. ํฌ๋„์ฃผ ์‹œ์‹

www.acmicpc.net/problem/2156 2156๋ฒˆ: ํฌ๋„์ฃผ ์‹œ์‹ ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹ํšŒ์— ๊ฐ”๋‹ค. ๊ทธ ๊ณณ์— ๊ฐ”๋”๋‹ˆ, ํ…Œ์ด๋ธ” ์œ„์— ๋‹ค์–‘ํ•œ ํฌ๋„์ฃผ๊ฐ€ ๋“ค์–ด์žˆ๋Š” ํฌ๋„์ฃผ ์ž”์ด ์ผ๋ ฌ๋กœ ๋†“์—ฌ ์žˆ์—ˆ๋‹ค. ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹์„ ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ์—ฌ๊ธฐ์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘ ๊ฐ€์ง€ ๊ทœ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ํฌ๋„์ฃผ ์ž”์˜ ๊ฐœ์ˆ˜ n์ด ์ฃผ์–ด์ง„๋‹ค. (1โ‰คnโ‰ค10,000) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ n+1๋ฒˆ์งธ ์ค„๊นŒ์ง€ ํฌ๋„์ฃผ ์ž”์— ๋“ค์–ด์žˆ๋Š” ํฌ๋„์ฃผ์˜ ์–‘์ด ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ํฌ๋„์ฃผ์˜ ์–‘์€ 1,000 ์ดํ•˜์˜ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ตœ๋Œ€๋กœ ๋งˆ์‹ค ์ˆ˜ ์žˆ๋Š” ํฌ๋„์ฃผ์˜ ์–‘์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ํฌ๋„์ฃผ๋ฅผ ๋งˆ์‹ค ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์€ ์–ด๋–ป๊ฒŒ ๋ ๊นŒ? dp๋ฅผ n๋ฒˆ์งธ ์ž”๊นŒ์ง€ ๋งˆ์‹ค ๋•Œ ๊ฐ€์žฅ ๋งŽ์€ ์–‘์˜ ํฌ๋„์ฃผ, grape๋ฅผ n๋ฒˆ์งธ ์ž”์˜ ํฌ๋„..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 10844๋ฒˆ. ์‰ฌ์šด ๊ณ„๋‹จ ์ˆ˜

www.acmicpc.net/problem/10844 10844๋ฒˆ: ์‰ฌ์šด ๊ณ„๋‹จ ์ˆ˜ ์ฒซ์งธ ์ค„์— ์ •๋‹ต์„ 1,000,000,000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— 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๊ฐœ ๊ทœ์น™์ด ๋ณด์ด๋Š”๊ฐ€? ๋ณด์ด์ง€ ์•Š์•„๋„ ๋œ๋‹ค. (๋ณธ์ธ๋„ ํ‘ธ๋Š”๋ฐ ์˜ค๋ž˜๊ฑธ๋ ธ์œผ๋‹ˆ... ์ด ๋ฌธ์ œ ๋งŽ์ด ์–ด๋ ค์› ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 1463๋ฒˆ. 1๋กœ ๋งŒ๋“ค๊ธฐ

www.acmicpc.net/problem/1463 1463๋ฒˆ: 1๋กœ ๋งŒ๋“ค๊ธฐ ์ฒซ์งธ ์ค„์— 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 106๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 10^6๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์—ฐ์‚ฐ์„ ํ•˜๋Š” ํšŸ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์šฐ์„  ๊ทœ์น™์„ ์ฐพ์•„๋ณด์ž. ๊ณ„์‚ฐ์‹์˜ ๊ฒฝ์šฐ ์—ฌ๋Ÿฌ๊ฐ€์ง€ ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๋‚˜์˜ฌ ์ˆ˜๋„ ์žˆ๋‹ค. N ์—ฐ์‚ฐ ํšŸ์ˆ˜ ๊ณ„์‚ฐ์‹ 1 1 1 2 1 2/2=1 3 1 3/3=1 4 2 (4-1)/3=1 5 3 (5-1)/2/2=1 6 2 6/3/2=1 7 3 (7-1)/3/2=1 8 3 8/2/2/2=1 9 2 9/3/3=1 10 3 (10-1)/3/3=1 ์–ด๋–ค ๊ทœ์น™์„ ์ฐพ์„ ์ˆ˜ ์žˆ์„๊นŒ? ์šฐ์„  ์ˆ˜๊ฐ€ 1์”ฉ ์ปค์งˆ ..

kodo_o
'C++' ํƒœ๊ทธ์˜ ๊ธ€ ๋ชฉ๋ก