๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ : https://www.acmicpc.net/problem/12852 12852๋ฒ: 1๋ก ๋ง๋ค๊ธฐ 2 ์ฒซ์งธ ์ค์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 106๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์ N์ด ์ฃผ์ด์ง๋ค. www.acmicpc.net ์ด๋ฒ ๋ฌธ์ ๋ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ(DP) ๋ฌธ์ ์์ต๋๋ค. 1463๋ฒ 1๋ก ๋ง๋ค๊ธฐ ๋ฌธ์ ์ ๋ค๋ฅธ ์ ์ n์ 1๋ก ๋ง๋๋ ๋ฐฉ๋ฒ์ ํฌํจ๋์ด ์๋ ์๋ค์ ์ญ์ถ์ ํ์ฌ ์ถ๋ ฅํ๋ฉด ๋ฉ๋๋ค. ๐ ใ๋ฌธ์ ํ์ดใ 1 ~ n ์ ๊ฐ ์ซ์๋ฅผ 1๋ก ๋ง๋ค๊ธฐ ์ํด ์ฐ์ฐ์ ํ๋ ํ์์ ์ต์๊ฐ์ dp ๋ฐฐ์ด์ ์ ์ฅํ๋ ค๊ณ ํจ 1. ์ซ์ 1์ ์ฐ์ฐ ํ์์ ์ต์๊ฐ์ 0 ์ด๋ฏ๋ก dp[1] = 0 2. 1์ ์ด์ ๊ฒฝ๋ก๋ ์กด์ฌํ์ง ์์ผ๋ฏ๋ก before[1] = -1 (๊ฒฝ๋ก ์ถ์ ์ ์ํ ๋ฐฐ์ด before) 3. ์ ์ n์ ์ฌ์ฉํ ์ ์..