2024/09 11
[BOJ] 1463๋ฒˆ: 1๋กœ ๋งŒ๋“ค๊ธฐ

โœ๏ธ ๋ฌธ์ œ์ •์ˆ˜ X์— ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ์—ฐ์‚ฐ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์„ธ ๊ฐ€์ง€ ์ด๋‹ค. X๊ฐ€ 3์œผ๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๋ฉด, 3์œผ๋กœ ๋‚˜๋ˆˆ๋‹ค.X๊ฐ€ 2๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๋ฉด, 2๋กœ ๋‚˜๋ˆˆ๋‹ค.1์„ ๋บ€๋‹ค. ์ •์ˆ˜ N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์œ„์™€ ๊ฐ™์€ ์—ฐ์‚ฐ ์„ธ ๊ฐœ๋ฅผ ์ ์ ˆํžˆ ์‚ฌ์šฉํ•ด์„œ 1์„ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ์—ฐ์‚ฐ์„ ์‚ฌ์šฉํ•˜๋Š” ํšŸ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•˜์‹œ์˜ค. ๐Ÿค– ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ ๐Ÿ’กํ’€์ด์ •๋ง ์œ ๋ช…ํ•œ DP ๋ฌธ์ œ ์ค‘ ํ•˜๋‚˜๋กœ, ์†”์งํžˆ ๋งํ•ด์„œ ๋ฌธ์ œ๋ฅผ ๋ณธ ์ ์€ ๋งŽ์€๋ฐ ์˜ค๋Š˜์„ ํฌํ•จํ•˜์—ฌ ์ž๋ ฅ์œผ๋กœ ํ‘ผ ์ ์€ ์—†๋‹ค. ์ฐธ ๋ถ€๋„๋Ÿฌ์šด ์ผ์ด์•ผ~ ์˜ค๋Š˜์„ DP ๊ณต๋ถ€์˜ ๋‚ ๋กœ ์ •ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์— ์•„์ฃผ ์„ธ์„ธํ•˜๊ฒŒ ์ฝ”๋“œ๋ฅผ ์ •๋ฆฌํ•ด๋ณด๋ ค๊ณ  ํ•œ๋‹ค. 1) ์ ‘๊ทผ ๋ฐฉ๋ฒ•1. DP ํ…Œ์ด๋ธ” ์ •์˜1์ฐจ์› ๋ฐฐ์—ด ํ˜•ํƒœ์˜ DP ํ…Œ์ด๋ธ” dp[i]์—๋Š” i๋ฅผ 1๋กœ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ์ตœ์†Œ ์—ฐ์‚ฐ ํšŸ์ˆ˜ ์ €์žฅ์˜ˆ) dp[3] = 1 (i=3์ด๊ณ  ..
Problem Solving/BOJ & Programmers 2024.09.03
1 2
๋”๋ณด๊ธฐ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”