ํ๋ จ์๋ก ๊ฐ๋ ๋ 1 [BOJ] 18858 : ํ๋ จ์๋ก ๊ฐ๋ ๋ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/18858 18858๋ฒ: ํ๋ จ์๋ก ๊ฐ๋ ๋ 1 ์ด์ M ์ดํ์ ์ ์๋ก ์ด๋ฃจ์ด์ง ๊ธธ์ด N์ ์์ด ์ค ๋ ผ์ฐ์ธ ๊ฒ์ ๊ฐ์๋ฅผ 998,244,353์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค. www.acmicpc.net ๋ ผ์ฐ(Non-์ฐ)์ธ ์์ด์ด ๋ช ๊ฐ์ธ์ง ์ถ๋ ฅํ๋ ๋ฌธ์ . ํ์ด ๋ ผ์ฐ์ด๋ Non-์ฐ ์ฆ ์ฐ์ด ์๋ ์์ด์ ์๋ฏธํ๋ค. a1 a3 ์ฒ๋ผ ์ฌ๋ผ๊ฐ๋ค ๋ด๋ ค๊ฐ๋ ํํ์ ์์ด์ ์ฐ์ด๋ผ๊ณ ๋ถ๋ฅด๊ธฐ๋ก ํ๋ค. ์ฌ๊ธฐ์ DP๋ฐฐ์ด์ ์ด๋ป๊ฒ ์ ์ธํ ์ง๊ฐ ๊ด๊ฑด์ธ๋ฐ, ์์ด์ i๋ฒ์งธ ์์ ๋ํด์ 3๊ฐ์ง์ ๊ฒฝ์ฐ๋ก ๋๋์ด์ ์๊ฐํ ์ ์๋ค. 1. i-1๋ฒ์งธ ์์ ๋น๊ตํ์ ๋ i๋ฒ์งธ ์๊ฐ ๋ ํฐ ๊ฒฝ์ฐ. ์ฆ, ์ฌ๋ผ์จ ๊ฒฝ์ฐ(์ค๋ฅด๋ง) 2. i-1๋ฒ์งธ ์์ ๋น๊ตํ์ ๋ i๋ฒ์งธ ์๊ฐ .. 2022. 4. 6. ์ด์ 1 ๋ค์