๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Python2

๋ฐฑ์ค€ 2293๋ฒˆ : ๋™์ „ 1 ๐Ÿ‘‰ ์ œ์ถœ ์ฝ”๋“œ import sys input = sys.stdin.readline n, k = map(int, input().split()) c = [int(input()) for i in range(n)] dp = [0 for i in range(k+1)] dp[0] = 1 for i in c: for j in range(i, k+1): if j-i >= 0: dp[j] += dp[j-i] print(dp[k]) ํ•ต์‹ฌ๋ฝ€์ธ๋œจ : * ๋™์  ๊ณ„ํš๋ฒ• (Dynamic Programming, DP) ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ ๊ณ ๋ คํ•ด์•ผํ•  ๊ฒƒ๋“ค '์ „์ฒด ๋ฌธ์ œ'๋ฅผ '๋ถ€๋ถ„ ๋ฌธ์ œ'๋กœ ์ž˜ ๋‚˜๋ˆ ์„œ ๋ฌธ์ œ๋ฅผ ์ ‘๊ทผํ–ˆ๋Š”๊ฐ€? ์ „์ฒด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๋ถ€๋ถ„ ๋ฌธ์ œ์˜ ์ ํ™”์‹์€ ๋ฌด์—‡์ธ๊ฐ€? ๋ถ€๋ถ„ ๋ฌธ์ œ๋“ค์„ ํ•ด๊ฒฐ ํ›„ ์–ป์€ ๊ฒฐ๊ณผ๊ฐ’๋“ค์„ ๋ฉ”๋ชจ์ด์ œ์ด์…˜ํ•˜์˜€๋Š”๊ฐ€? ๋ถ€๋ถ„.. 2023. 8. 17.
๋ฐฑ์ค€ 11650๋ฒˆ : ์ขŒํ‘œ ์ •๋ ฌํ•˜๊ธฐ (python) ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด์„œ ์•Œ ์ˆ˜ ์žˆ๋Š” ์  : 1. 2์ฐจ์› ํ‰๋ฉด ์œ„์˜ ์  N๊ฐœ → 2์ฐจ์› ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•ด๋ณผ๊นŒ? 2. ์ขŒํ‘œ๋ฅผ x์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ 3. x์ขŒํ‘œ๊ฐ€ ๊ฐ™์œผ๋ฉด, y์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ 4. ์ •๋ ฌ → sorted(), sort() ํ•จ์ˆ˜ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ์Œ ํ•„์š”ํ•œ ์ž…๋ ฅ๊ฐ’ : 1. ์ฒซ์งธ ์ค„ : ์ ์˜ ๊ฐœ์ˆ˜ N 2. ๋‘˜์งธ ์ค„ ~ : i๋ฒˆ์ ์˜ ์œ„์น˜ xi์™€ yi (์œ„์น˜๊ฐ€ ๊ฐ™์€ ๋‘ ์ ์€ ์—†๋‹ค) → ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ์ž…๋ ฅ ๊ฐ’์„ ๋ฐ›๋Š” ๊ฒƒ์ด๋ฏ€๋กœ ๋ฐ˜๋ณต๋ฌธ ๋Œ๋ ค์•ผ๋จ ํŒŒ์•… ๊ฐ€๋Šฅ ์ถœ๋ ฅ๊ฐ’ : 1. ์ฒซ์งธ ์ค„ ~ N๊ฐœ์˜ ์ค„์— ์ ์„ ์ •๋ ฌํ•œ ๊ฒฐ๊ณผ → (ํ•œ ์ค„๋กœ ๋ฐฐ์—ด์„ ๋ณด์—ฌ์ฃผ๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๊ณ ) ๊ฐ i๋ฒˆ์งธ ๋ฐฐ์—ด์˜ ์š”์†Œ๋ฅผ ์ฐจ๋ก€๋Œ€๋กœ ์ถœ๋ ฅํ•ด์•ผํ•จ์„ ๋ณด๊ณ  ์ด ๋˜ํ•œ ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ๋ ค์„œ ์ถœ๋ ฅ์„ ํ•ด์•ผํ•˜๋Š”๊ตฌ๋‚˜ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ์Œ ๐Ÿ‘‰ ํŒŒ์•…ํ•œ ๊ฒƒ์„ ๋ฐ”ํƒ•์œผ๋กœ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•ด๋ณด์ž! STE.. 2023. 5. 19.