๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ

๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ/BAEKJOON\๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ

๋ฐฑ์ค€ 9465๋ฒˆ (DP) - ์Šคํ‹ฐ์ปค (JAVA) ๋ฌธ์ œ ํ’€์ด

https://www.acmicpc.net/problem/9465 9465๋ฒˆ: ์Šคํ‹ฐ์ปค ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” n (1 ≤ n ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ ๋‘ ์ค„์—๋Š” n๊ฐœ์˜ ์ •์ˆ˜๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ๊ฐ ์ •์ˆ˜๋Š” ๊ทธ ์œ„์น˜์— ํ•ด๋‹นํ•˜๋Š” ์Šคํ‹ฐ์ปค์˜ www.acmicpc.net โœ๏ธ ๋ฌธ์ œ ๐Ÿ” ๋ฌธ์ œ ํ•ด๊ฒฐ ํ•ด๋‹น ๋ฌธ์ œ๋Š” 2xN ์Šคํ‹ฐ์ปค๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์Šคํ‹ฐ์ปค๋ฅผ ๊ณจ๋ผ ๊ฐ€์žฅ ๋†’์€ ์ ์ˆ˜์˜ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ด๋•Œ ๊ณ ๋ฅธ ์Šคํ‹ฐ์ปค์˜ ์ขŒ,์šฐ,์ƒ,ํ•˜ ์Šคํ‹ฐ์ปค๋Š” ์„ ํƒํ•  ์ˆ˜ ์—†๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์›๋ž˜ ์ด ๋ฌธ์ œ๋Š” ๊ฐ€๋กœ๋กœ arr[0][0] -> arr[0][1] ... -> arr[1][N] ์ด๋Ÿฐ ์‹์œผ๋กœ ์ง„ํ–‰ํ•˜๋ฉด์„œ ๊ณ„์‚ฐํ•˜๋ ค ํ–ˆ๋”๋‹ˆ ์‹คํŒจํ•˜์—ฌ์„œ ์„ธ๋กœ (arr[0][1] -> arr[1][1] -..

๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ/BAEKJOON\๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ

๋ฐฑ์ค€ 15486๋ฒˆ (DP) - ํ‡ด์‚ฌ 2 (JAVA) ๋ฌธ์ œ ํ’€์ด

https://www.acmicpc.net/problem/15486 15486๋ฒˆ: ํ‡ด์‚ฌ 2 ์ฒซ์งธ ์ค„์— N (1 ≤ N ≤ 1,500,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— Ti์™€ Pi๊ฐ€ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด์„œ ์ฃผ์–ด์ง€๋ฉฐ, 1์ผ๋ถ€ํ„ฐ N์ผ๊นŒ์ง€ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net โœ๏ธ ๋ฌธ์ œ ํ•ด๋‹น ๋ฌธ์ œ๋Š” ๋ฐฑ์ค€ 14501๋ฒˆ (DFS) - ํ‡ด์‚ฌ ๋ฌธ์ œ์™€ ๊ฐ™์ง€๋งŒ, ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(N) ์œผ๋กœ ํ•ด๊ฒฐ์„ ํ•ด์•ผ ํ†ต๊ณผํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. 14501๋ฒˆ: ํ‡ด์‚ฌ ์ฒซ์งธ ์ค„์— ๋ฐฑ์ค€์ด๊ฐ€ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ด์ต์„ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net ๐Ÿ” ๋ฌธ์ œ ํ•ด๊ฒฐ ์ด๋ฒˆ์—๋Š” DP๋กœ ๋ฌธ์ œ๋ฅผ ํ’€์–ด์•ผํ•ฉ๋‹ˆ๋‹ค. ์ฐจ๊ทผ์ฐจ๊ทผ ํ•จ๊ป˜ ์‚ดํŽด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. 1. ํ…Œ์ด๋ธ” ์ •์˜ ๋จผ์ € dp[i]๋ฅผ..

๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ/BAEKJOON\๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ

๋ฐฑ์ค€ 10844๋ฒˆ (DP) - ์‰ฌ์šด ๊ณ„๋‹จ ์ˆ˜ (JAVA) ๋ฌธ์ œ ํ’€์ด

10844๋ฒˆ: ์‰ฌ์šด ๊ณ„๋‹จ ์ˆ˜ (acmicpc.net) 10844๋ฒˆ: ์‰ฌ์šด ๊ณ„๋‹จ ์ˆ˜ ์ฒซ์งธ ์ค„์— ์ •๋‹ต์„ 1,000,000,000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net โœ๏ธ ๋ฌธ์ œ ๐Ÿ” ๋ฌธ์ œ ํ•ด๊ฒฐ 1. ํ…Œ์ด๋ธ” ์ •์˜ dp[i][j]๋Š” ๊ธธ์ด๊ฐ€ i์ด๊ณ , j๋กœ ์‹œ์ž‘ํ•˜๋Š” ์ˆ˜๋“ค ์ค‘ ๊ณ„๋‹จ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๋œปํ•ฉ๋‹ˆ๋‹ค. ์„ค๋ช…์ด ๋ถ€์กฑํ•œ ๋“ฏ ํ•ด๋ณด์—ฌ ์•„๋ž˜์˜ ํ‘œ ํ˜•ํƒœ๋กœ ํ‘œํ˜„ํ•ด๋ณด์•˜์Šต๋‹ˆ๋‹ค. 0์œผ๋กœ ์‹œ์ž‘ํ•˜๋Š” ์ˆ˜๋Š” ์—†๋‹ค๊ณ  ์กฐ๊ฑด์— ๋‚˜์™€์žˆ์ง€๋งŒ, ์ ํ™”์‹์„ ์„ธ์šฐ๊ธฐ ์œ„ํ•ด์„œ๋Š” 0์œผ๋กœ ์‹œ์ž‘ํ•˜๋Š” ๊ณ„๋‹จ ์ˆ˜๋„ ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค. dp[i][j]์—๋Š” ์œ„ ํ‘œ์—์„œ ์ •์˜ํ•œ ๋Œ€๋กœ ๊ฐœ์ˆ˜๊ฐ€ ๋“ค์–ด๊ฐˆ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ ์ค‘์š”ํ•œ ํฌ์ธํŠธ๋Š” dp[1][0] = 0์ด๋ผ๊ณ  ํ•ด์„œ ๊ฐœ์ˆ˜๊ฐ€ 0์ด ์•„๋‹™๋‹ˆ๋‹ค! 1๊ฐœ๋กœ ์ฒดํฌํ•ด์ค˜์•ผ ์•„๋ž˜ ์ ํ™”์‹์ด ์„ฑ๋ฆฝํ•ฉ๋‹ˆ๋‹ค. 2. ์ ํ™”์‹ ์„ธ์šฐ๊ธฐ ์œ„ ํ‘œ๋ฅผ ์ฐธ๊ณ ํ•˜..

๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ/BAEKJOON\๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ

๋ฐฑ์ค€ 11053๋ฒˆ (DP) - ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด (JAVA) ๋ฌธ์ œ ํ’€์ด

https://www.acmicpc.net/problem/11053 11053๋ฒˆ: ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด ์ˆ˜์—ด A๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ˆ˜์—ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์šฐ์— ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์€ A = {10, 20, 10, 30, 20, 50} ์ด www.acmicpc.net โœ๏ธ ๋ฌธ์ œ ๐Ÿ” ๋ฌธ์ œ ํ•ด๊ฒฐ ๋ฌธ์ œ๋ฅผ ์ดํ•ดํ•˜์ง€ ๋ชปํ•ด์„œ ํ—ค๋งธ๋˜ ๋ฌธ์ œ์ด๋‹ค.. ์•„๋ž˜ ์„ค๋ช…๊ณผ ํ•จ๊ป˜ ํ’€์ด๋ฅผ ํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. 1. ํ…Œ์ด๋ธ” ์ •์˜ 1์ฐจ์› ๋ฐฐ์—ด dp[i]๋Š” i ๋ฒˆ์งธ ์ˆ˜๊นŒ์ง€์˜ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ์ˆ˜์—ด์˜ ๊ธธ์ด๋ฅผ ๋œปํ•ฉ๋‹ˆ๋‹ค. ์•„์ง ์ž˜ ์ดํ•ด๊ฐ€ ์•ˆ๋˜์‹œ๋Š” ๋ถ„๋“ค์„ ์œ„ํ•ด ์•„๋ž˜ ์ฝ”๋“œ๋กœ ์„ค๋ช…ํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. 10 20 30 20 30 dp[0] = ..

๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ/BAEKJOON\๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ

๋ฐฑ์ค€ 2156๋ฒˆ (DP) : ํฌ๋„์ฃผ ์‹œ์‹ (JAVA) ๋ฌธ์ œ ํ’€์ด

https://www.acmicpc.net/problem/2156 2156๋ฒˆ: ํฌ๋„์ฃผ ์‹œ์‹ ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹ํšŒ์— ๊ฐ”๋‹ค. ๊ทธ ๊ณณ์— ๊ฐ”๋”๋‹ˆ, ํ…Œ์ด๋ธ” ์œ„์— ๋‹ค์–‘ํ•œ ํฌ๋„์ฃผ๊ฐ€ ๋“ค์–ด์žˆ๋Š” ํฌ๋„์ฃผ ์ž”์ด ์ผ๋ ฌ๋กœ ๋†“์—ฌ ์žˆ์—ˆ๋‹ค. ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹์„ ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ์—ฌ๊ธฐ์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘ ๊ฐ€์ง€ ๊ทœ www.acmicpc.net โœ๏ธ ๋ฌธ์ œ ๐Ÿ” ๋ฌธ์ œ ํ•ด๊ฒฐ ๋‚˜๋ž€ํžˆ ๋†“์—ฌ์žˆ๋Š” ํฌ๋„์ฃผ๋ฅผ ๋งˆ์…”์„œ ๊ฐ€์žฅ ๋งŽ์ด ๋งˆ์‹  ์–‘์„ ์ถœ๋ ฅํ•˜๋ฉด ๋˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ ๋ณด๋ฉด์„œ ๊ณ„๋‹จ์˜ค๋ฅด๊ธฐ ๋ฌธ์ œ์™€ ์œ ์‚ฌํ•˜์—ฌ ํ•ด๋‹น ๋ฌธ์ œ ํ’€์ด ๋ฐฉ์‹๋Œ€๋กœ ํ‘ผ๋‹ค๋ฉด ํ‹€๋ฆฌ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ด๋ฒˆ ๋ฌธ์ œ์—๋Š” ํฌ๋„์ฃผ๋ฅผ ๋งˆ์‹œ์ง€ ์•Š๋Š” ๊ฒฝ์šฐ๋„ ์žˆ์„ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ํ•ด๋‹น ๊ฒฝ์šฐ๋„ ์ž˜ ์ƒ๊ฐํ•ด์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋ฌธ์ œ์—์„œ ์ฃผ์–ด์ง„ ์˜ˆ์ œ๋ฅผ ์‚ดํŽด๋ณด๋ฉด, ๊ฐ€์žฅ ๋งŽ์ด ๋งˆ์‹ค ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์€ ์•„๋ž˜์™€ ๊ฐ™์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ฒซ ๋ฒˆ์งธ, ๋‘ ..

๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ/BAEKJOON\๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ

๋ฐฑ์ค€ 1003๋ฒˆ(DP) - ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜ (JAVA) ๋ฌธ์ œ ํ’€์ด

https://www.acmicpc.net/problem/1003 1003๋ฒˆ: ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜ ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค 0์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜์™€ 1์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜๋ฅผ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด์„œ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net โœ๏ธ ๋ฌธ์ œ ๐Ÿ” ๋ฌธ์ œ ํ•ด๊ฒฐ 1. ํ…Œ์ด๋ธ” ์ •์˜ dp[i][j]์˜ i๊ฐ’์€ i ๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋ฅผ ์˜๋ฏธํ•˜๊ณ , j(=0, 1)๋Š” ํ•ด๋‹น ํ”ผ๋ณด๋‚˜์น˜์ˆ˜์˜ 0์˜ ์ถœ๋ ฅ ํšŸ์ˆ˜์™€ 1์˜ ์ถœ๋ ฅ ํšŸ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค. dp[i][0] = i ๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์˜ 0 ์ถœ๋ ฅ ํšŸ์ˆ˜ dp[i][1] = i ๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์˜ 1 ์ถœ๋ ฅ ํšŸ์ˆ˜ 2. ์ ํ™”์‹ ์„ธ์šฐ๊ธฐ 3 ๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์— ๋Œ€ํ•ด์„œ ์ƒ๊ฐํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. fibonacci(3)์€ fibonacci(2) + fibonacci(1) ์ž…๋‹ˆ๋‹ค. fibonacci(2)๋Š” fibonacci(0..

iseunghan
'๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก