[python]๋ฐฑ์ค€ 1463๋ฒˆ : 1๋กœ ๋งŒ๋“ค๊ธฐ
Algorithm ๋ฌธ์ œ/BOJ 2020. 2. 1. 11:01

https://www.acmicpc.net/problem/1463 ๋‚˜์˜ ๋‹ต ์—ฐ์‚ฐ์˜ ์šฐ์„ ์ˆœ์œ„๋ฅผ ๋งค๊ฒผ์Œ 1๋นผ๊ธฐ 1๋นผ๊ณ  2๋‚˜๋ˆ„๊ธฐ ์ด๋Ÿฌํ•œ ๊ฐ€์ •์„ ์˜ˆ์ œ ๊ณ„์‚ฐ๋งŒ์œผ๋กœ ํ™•์ •ํ•œ๋Œ€์„œ ๋ฌธ์ œ๊ฐ€ ์žˆ์—ˆ์ง€ ์•Š๋‚˜ ์‹ถ๋‹ค. ์—ฐ์‚ฐ์— ์šฐ์„ ์ˆœ์œ„๋ฅผ ๋‘๋Š” ๊ฒƒ์€ ์˜๋ฏธ๊ฐ€ ์—†์Œ ๋‹ค๋ฅธ ๋‹ต (2020-04-19 ์ˆ˜์ •) ๋™์  ๊ณ„ํš๋ฒ•(Dynamic programming)์„ ์ด์šฉํ•˜๋Š” ๋ฐฉ๋ฒ• ๋™์  ๊ณ„ํš๋ฒ•์€ ์–ด๋–ค ๋ฌธ์ œ์˜ ๋‹ต์„ ๋ฉ”๋ชจ๋ฆฌ์— ์ €์žฅํ•ด๋‘์—ˆ๋‹ค๊ฐ€ ๋‹ค์‹œ ๊ฐ’์„ ๊ตฌํ•ด์•ผํ•  ๋•Œ ์ค‘๋ณต๊ณ„์‚ฐ์ด ํ•„์š”์—†๊ฒŒ ๊ฐ€์ ธ๋‹ค ์“ฐ๋Š” ๊ธฐ๋ฒ•์ด๋‹ค. x = int(input()) count = 0 minimum = [x] def cal(x): # ์ฃผ์–ด์ง„ ํ–‰๋ ฌ์˜ ๋ชจ๋“  ์ˆ˜ ๊ฐ๊ฐ์— ๋Œ€ํ•ด์„œ -1, 3์œผ๋กœ ๋‚˜๋ˆ„๊ธฐ, 2๋กœ ๋‚˜๋ˆ„๊ธฐ์˜ 3๊ฐ€์ง€ ์—ฐ์‚ฐ์„ ๋ชจ..