๋ชฉ๋ก์ ์ฒด ๊ธ (1096)
KoreanFoodie's Study
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ํ .. ์ด ์ ๋๊ฐ? [์ข ๋ง๋ถ ๋ฌธ์ ] ๋๋๋ฐ ๋ฐ์ฌ์ ํ์ฅ (๋ฌธ์ ID : NUMB3RS, ๋์ด๋ : ์ค) ์ฌ๊ธฐ๊น์ง ์์ผ๋ฉด, ์ด์ DP ๋ฌธ์ ๋ ํจํด์ด ํ์ต๋์์ ๊ฒ์ด๋ค. ๊ทธ๋ฅ... ์๋์ฒ๋ผ ํ๋ฉด ๋๋ฌ๊น์(์์). #include #include "stdlib.h" #include #include #include #include #include using namespace std; /*************************************************************************************..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ์ธ๋ป ๋ถ๊ฐ๋ฅํด ๋ณด์ด๋ ๋ฌธ์ ๋, ๋ฌธ์ ์ ์กฐ๊ฑด์ ์ ๋ณด๋ฉด ๋ถ๋ถ ๋ฌธ์ ์ ์กฐํฉ์ผ๋ก ๋ถํดํด ๋ณผ ์ ์๋ค! [์ข ๋ง๋ถ ๋ฌธ์ ] ํด๋ฆฌ์ค๋ฏธ๋ ธ (๋ฌธ์ ID : POLY, ๋์ด๋ : ์ค) ํด.. ๋งจ ์ฒ์์๋ ๋ฌด์จ ๋ฌธ์ ์ธ๊ฐ ์ถ์์ง๋ง, ๊ฒฐ๊ตญ ํ์ด๋ด์ ์ฑ์ทจ๊ฐ์ด ์๋ ๋ฌธ์ ์๋ค. ์ฑ ์ ์๋ ์ ๊ทผ๋ฒ์ ์กฐ๊ธ ๊ฐ์ ธ์ ๋ณด์๋ฉด... ์์ ์ฑ์ง์ ์ด์ฉํด์ ์ ํ์์ ์ธ์ฐ๋ฉด ๋๋ค. ์ ์ด๋ ๊ฒ ๋๋๋ฉด, ํ ์ค์ ์๋ ๋ธ๋ญ๋ค์ ์๋ก ๋จ์ด์ ธ ์์ผ๋ฉด ์๋๊ณ ๋ถ์ด ์์ด์ผ ํ๋ ์ฑ์ง ๋๋ฌธ์ด๋ค! ๐ ์ ํ์์ ๋๋ต ์๋์ฒ๋ผ ์๊ฒผ๋ค. ๋ ๊ฐ์ ๊ฒฝ์ฐ, ์ฒ์์๋ ์๋์ฒ๋ผ for-loop ์ผ๋ก..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ์ ๋น๋ก์ด ๋์ ๊ณํ๋ฒ์ ์ธ๊ณ... ์ธ๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง์ผ ์ ์๋ค. [์ข ๋ง๋ถ ๋ฌธ์ ] ๋น๋์นญ ํ์ผ๋ง (๋ฌธ์ ID : ASYMTILING, ๋์ด๋ : ํ) ์ฌ์ค ์ด ๋ฌธ์ ๋ ์ด์ ์ ํ์ผ๋ง ๋ฌธ์ ์ ๋งค์ฐ ๋น์ทํ๋ค. ์ค์ํ ๊ฑด '๋์นญ์ธ ๊ฒฝ์ฐ๋ฅผ ์ด๋ป๊ฒ ๋บผ ๊ฒ์ธ๊ฐ?' ์ธ๋ฐ, ์ ์๊ฐํด ๋ณด๋ฉด ๊ธธ์ด๊ฐ ํ์์ผ ๋์ ์ง์์ผ ๋๋ฅผ ๋๋ ์ ๊ฐ๋จํ ์ฐ์ฐ์ ํด ์ฃผ๋ฉด ๋๋ค๋ ๊ฒ์ ์ ์ ์๋ค. ์ฌ์ค ๊ทธ๋ค์ง ๊น๋ํ์ง๋ ์์ง๋ง, ๋๋ ์๋ ์ฝ๋์ฒ๋ผ ํ์๋ค. #include #include "stdlib.h" #include #include #include #i..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ์์ํด์ ์ฃฝ๊ณ ์ถ์ด์ก๋ค. [์ข ๋ง๋ถ ๋ฌธ์ ] ๋ฌํฝ์ด (๋ฌธ์ ID : SNAIL, ๋์ด๋ : ํ) ์ฌ์ด DP ๋ฌธ์ ๋ค. ์ ํ์๋ง ์ ์ธ์ฐ๋ฉด ๋๋๋ฐ... ์ฑ ์์๋ ์๋์ฒ๋ผ ๋ง๋ค๋๋ผ. ๋ ๊ฐ์ ๊ฒฝ์ฐ, ์๋์ ๊ฐ์ด ํ์๋ค. ์ ํ์์ ์๋ฆฌ๋ ๊ฑฐ์ ๋์ผํ๋ค! #include #include "stdlib.h" #include #include #include #include #include using namespace std; /******************************************************************..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ๊ฐ๋จํ DP ๋ฌธ์ ์ง๋ง.. ์ฌ๊ท๋ก๋ ํ์ด๋ณด์. [์ข ๋ง๋ถ ๋ฌธ์ ] ์ผ๊ฐํ ์์ ์ต๋ ๊ฒฝ๋ก ์ ์ธ๊ธฐ (๋ฌธ์ ID : TRIPATHCNT, ๋์ด๋ : ์ค) ์ด๋ฒ ๋ฌธ์ ๋, ๊ฐ๋จํ๊ฒ DP ๋ก ํ ์ ์๋ค. ์๋ฅผ ๋ค์ด ๋ค์๊ณผ ๊ฐ๋ค. #include #include "stdlib.h" #include #include #include #include using namespace std; /*****************************************************************************************..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ๊ฐ๋จํ DP ๋ฌธ์ ๋ค. [์ข ๋ง๋ถ ๋ฌธ์ ] ํ์ผ๋ง (๋ฌธ์ ID : TILING2, ๋์ด๋ : ํ) ๊ฐ๋จํ DP ๋ฌธ์ ๋ค. #include #include "stdlib.h" #include #include #include #include using namespace std; /****************************************************************************************************/ int N; int cache[101]; void preCalc() { for (..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ์ต์ ๋ถ๋ถ ๋ฌธ์ ๋ฅผ ์ฐพ๋ ๊ฒ์ ๊ฐํน, ๋งค์ฐ ์ฝ์ง ์์ ์ผ์ด๋ค... ๋ฌด์ํ๊ฒ ํธ๋ ์ ๋ฒ๋ถํฐ ์์ํ๋ฉด ํฐ์ฝ๊ฐ ๋ค์น ์ ์๋ค. ๊ทผ๋ฐ ๋ ์ฝ ๋ฎ์๋ฐ.. ์ด์จ๋ ๋ค์ณค๋ค. [์ข ๋ง๋ถ ๋ฌธ์ ] Quantization (๋ฌธ์ ID : QUANTIZE, ๋์ด๋ : ์ค) ์ด ๋ฌธ์ ๋ ์์ด๋์ด๊ฐ ํ์ํ๋ค. ๋จ์ํ ์์ด์ ์ ๋ ฌํ ๋ค์์, ์ซ์๋ฅผ ์ต์๊ฐ์์ ์ต๋๊ฐ๊น์ง ๋ฃ๋ ๋ฐฉ์์ผ๋ก๋ ํ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค. ๊ทธ๋ฐ๋ฐ ์ด๋ ๊ฒ ๋ฌถ์ด๋ณด๋ฉด ์ด๋จ๊น? ์ด๋ ๊ฒ ๋ฌถ์ด ๋๊ณ ๋ณด๋ฉด, ์ธ์ ํ ์ซ์๋ผ๋ฆฌ ์ ์ ํ ๋ฌถ๊ณ , ์ต์ ์ค์ฐจ๋ฅผ ๋ด๋ ์๋ฅผ ์ฐพ๋ ๋ฌธ์ ๋ก ๋ณํํ ์ ์๋ค! ๊ทธ๋ผ ์๋์ ..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ์์ฃผ์จ ๊ฐ์๊ฑฐ ์ข ์ธ์ฐ๊ณ ๋ค๋์ง ๋ง์; [์ข ๋ง๋ถ ๋ฌธ์ ] ์์ฃผ์จ ์ธ์ฐ๊ธฐ (๋ฌธ์ ID : PI, ๋์ด๋ : ํ) ๋ฌธ์ ์์ฒด๋ ์ด๋ ต์ง ์๋ค! ๊ทธ๋ฅ ์ ํ์๋ง ์ ์ธ์ฐ๋ฉด ๋๋๋ฐ... ์ผ๋จ ์ฝ๋๋ฅผ ๋ณด์. #include #include "stdlib.h" #include #include #include using namespace std; int N; vector arr; vector cache; int diff(int i, int j) { if (i > j) return 0; if (j >= N) return 10; if ((j - i ..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ์ ํ์์ ์ ์ธ์๋ณด์. [์ข ๋ง๋ถ ๋ฌธ์ ] ํฉ์น LIS (๋ฌธ์ ID : JLIS, ๋์ด๋ : ํ) ์ด๊ฒ๋ LIS ์ ๋น์ทํ ๋ก์ง์ ์ ์ฉํ๋ฉด ๋๋ค. ์ผ๋จ, jlis ํจ์๋ฅผ ๋ค์๊ณผ ๊ฐ์ด ์ ์ํ ๊ฒ์ด๋ค. jlis(indexA, indexB) = A[indexA] ์ B[indexB] ์์ ์์ํ๋ ํฉ์น ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ์ต๋ ๊ธธ์ด ์์๋ฅผ ๋ฑํ ์ง์ ํ์ง๋ ์์์ผ๋ A[indexA] ์B[indexB] ์ค ์์ ์ชฝ์ด ์์ ์จ๋ค๊ณ ๊ฐ์ ํ์. ๊ทธ๋ผ ์ ํ์์ ์๋์ ๊ฐ์ด ์ธ์ธ ์ ์๋ค. ๊ทธ๋ผ ์์ ์ ํ์์ ์ค์ ๋ก ๊ตฌํํด ๋ณด์! ๐ #include ..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ๋จผ์ ์์ ํ์๋ถํฐ ์์ํด๋ณด์. ๊ทธ ํ, ์ ์ฒด ๋ต์ ์ ์๋ฅผ ๋ฐํํ๋ ๊ฒ์ด ์๋๋ผ ์์ผ๋ก ๋จ์ ์ ํ๋ค์ ํด๋นํ๋ ์ ์๋ง์ ๋ฐํํ๋๋ก ๋ถ๋ถ ๋ฌธ์ ์ ์๋ฅผ ๋ฐ๊พธ์. 2. ์ฌ๊ท ํธ์ถ์์ ์ด์ ์ ์ ํ๊ณผ ๊ด๋ จ๋ ์ ๋ณด๋ ์ต๋ํ ์ค์ด์. ๊ทธ๋ผ์ผ๋ก์จ, ์ฐ๋ฆฌ๋ ์ต๋ํ ์ค๋ณต๋๋ ๋ฌธ์ ๋ฅผ ๋ง์ด ๋ง๋ค์ด๋ผ ์ ์๋ค. [์ข ๋ง๋ถ ๋ฌธ์ ] ์ต๋ ์ฆ๊ฐ ๋ถ๋ถ ์์ด (๋ฌธ์ ID : LIS, ๋์ด๋ : ํ) ์ผ๋จ, ์๋์ ๊ฐ์ด ๊ฐ๋จํ๊ฒ for-loop ์ผ๋ก ํ์ด๋ณผ ์ ์๋ค. #include #include "stdlib.h" #include #include using n..