Algorithm/BOJ
2022. 3. 9.
[BOJ] 2xn ํ์ผ๋ง(11726)
[๋ฐฑ์ค(BOJ)] 2xn ํ์ผ๋ง(11726) C++ ๋ฌธ์ : BOJ_11726๋ฒ 2xn ํ์ผ๋ง ๋ฌธ์ ์ค๋ช
DP DP๋ฅผ ํ์ฉํ์ฌ ํด๊ฒฐํ ์ ์๋ ๊ธฐ๋ณธ๋ฌธ์ ์
๋๋ค. 2X1, 1X2 ํฌ๊ธฐ์ ๋ธ๋ก์ด ์๊ณ , n์ด ์ฃผ์ด์ง๋๋ค. ์ด๋ 2Xn ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ์ ๋ธ๋ก์ ์ด์ฉํด ์ฑ์ฐ๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ์ถ๋ ฅํด์ผ ํฉ๋๋ค ๋ฐฉ๋ฒ์ ์๊ฐ ์ปค์ง๋ฏ๋ก 10,007๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํด์ผ ํฉ๋๋ค. Solution n์ ํฌ๊ธฐ๊ฐ 1์ด๋ผ๋ฉด, 1X2 ์ ๋ธ๋ก ํ๋๋ฅผ ์ธ์ฐ๋ 1๊ฐ์ง ๊ฒฝ์ฐ์ ์ ๋ฐ์ ์์ต๋๋ค. n์ ํฌ๊ธฐ๊ฐ 2๋ผ๋ฉด, 1X2 ์ ๋ธ๋ก ๋ ๊ฐ๋ฅผ ์ธ์ฐ๋ ๊ฒฝ์ฐ์ ์, 2X1 ์ ๋ธ๋ก ๋ ๊ฐ๋ฅผ ์๋ ๊ฒฝ์ฐ์ ์, ์ด 2๊ฐ์
๋๋ค. n์ ํฌ๊ธฐ๊ฐ 3 ์ด์ ์ผ ๋, DP๋ฅผ ์ ์ฉํ ์ ์๋ ๊ท์น์ด ์์ต๋๋ค. ๊ฐ์ฅ ์ค๋ฅธ์ชฝ n ๋ฒ ์งธ ์นธ์ 1X2 ์ ๋ธ๋ก ํ๋..