๋ชฉ๋ก์ ์ฒด ๊ธ (1096)
KoreanFoodie's Study
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ํ๋ฒํ DP ๋ฌธ์ ๋ก, for-loop ํน์ ์ฌ๊ทํจ์๋ก ํ ์ ์๋ค. [์ข ๋ง๋ถ ๋ฌธ์ ] ์ผ๊ฐํ ์์ ์ต๋ ๊ฒฝ๋ก (๋ฌธ์ ID : TRIANGLEPATH, ๋์ด๋ : ํ) ์ผ๋จ for-loop ์ผ๋ก ํผ ๋ฒ์ ์ ๋ณด์. #include #include "stdlib.h" #include #include using namespace std; int N; int tri[100][100]; int cache[100][100]; void sol() { cache[0][0] = tri[0][0]; for (int i = 1; i < N; ++i) ..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. DP ๋ฌธ์ ๋ ์ค๋ณต ๊ณ์ฐ๋๋ ๊ฒ์ด ๋ฌด์์ธ์ง ์ฒดํฌํ๋ ๊ฒ์ด ์ค์ํ๋ค. [์ข ๋ง๋ถ ๋ฌธ์ ] ์์ผ๋์นด๋ (๋ฌธ์ ID : WILDCARD, ๋์ด๋ : ์ค) ์ผ๋จ DP ๋ฅผ ์ด์ฉํด์ ํ ๋ฒ ํ์ด๋ณด์๋ค. ๋ถ๋๋ฝ์ง๋ง ๋๋ ์ฒ์์ ์ด๋ ๊ฒ ํ์๋ค : #include #include "stdlib.h" #include #include #include #include using namespace std; /************************************************************************************..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. DP ๋ฌธ์ ๋ฅผ ํ ๋๋, ๋จผ์ ์์ ํ์์ผ๋ก ํ ์ ์๋์ง ์ฒดํฌ๋ฅผ ํด ๋ณด๊ณ , ๋ฉ๋ชจ์ด์ฌ์ด์ ์ด ๊ฐ๋ฅํ์ง๋ฅผ ํ์ ํ๋ ๊ฒ๋ ์ข์ ์ ๊ทผ ๋ฐฉ๋ฒ์ด๋ค. [์ข ๋ง๋ถ ๋ฌธ์ ] ์ธ๋ฐ ๋ฐ๊ธฐ (๋ฌธ์ ID : JUMPGAME, ๋์ด๋ : ํ) ๋ฐ๋ก.. ์์ ์ฝ๋๋ก ๋ค์ด๊ฐ ๋ณด์. #include #include "stdlib.h" #include #include #include using namespace std; /*********************************************************************************..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ๋ฌด์ํ๊ฒ ํ๋ฉด, ์๊ฐ ๋ณต์ก๋๊ฐ O(N^2) ๊ฐ ๋์ด ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค. 2. ์นด๋ผ์ธ ๋ฐ์ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด ๋ณด์! [์ข ๋ง๋ถ ๋ฌธ์ ] ํฌ๋ฏธํ (๋ฌธ์ ID : FANMEETING, ๋์ด๋ : ์) ํฌ๋ฏธํ ๋ฌธ์ ๋ ์ข ๋ง๋ถ์์ ์ฒ์์ผ๋ก ๋์ค๋ '์' ๋์ด๋์ ๋ฌธ์ ์ด๋ค. ํ์ง๋ง ๊ฑฑ์ ํ์ง ๋ง๋ผ. ์์ ๋๋ณด๋ค ๋น ๋ฅด๋๊น... ๊ทผ๋ฐ ์ฌ์ค ์์ด ๋น ๋ฅธ ๊ฑด ๋ณ๋ก ๋์์ด ์๋๋ค. ์ด์จ๋ , ์ด ๋ฌธ์ ๋ '๋ฌด์ํ๊ฒ' ํผ๋ค๊ณ ํ๋ฉด O(N^2) ๋ก ํ์ด๋ณผ ์๋ ์์ ๊ฒ์ด๋ค. ์์ ์ฝ๋๋ ์๋์ ๊ฐ๋ค(์๊ฐ์ด๊ณผ ํจ์ ์ ์). #include #include "stdl..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ๋ถํ ์กฐ๊ฑด์ ์ ๋ฐ์ ธ๋ณด์. [์ข ๋ง๋ถ ๋ฌธ์ ] ์ธํ๋ฆฌ ์๋ผ๋ด๊ธฐ (๋ฌธ์ ID : FENCE, ๋์ด๋ : ์ค) ์ด ๋ฌธ์ ๋ ์๋์ฒ๋ผ ๋ฌด์ํ๊ฒ ํ๋ฉด O(N^2) ์ ํ ์๋ ์์ง๋ง, ์๊ฐ์ด๊ณผ๊ฐ ๋๋ค. ๐ ์ด๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด, ์ฐ๋ฆฌ๋ ๋ถํ ์ ๋ณต์ ์ฌ์ฉํ ๊ฒ์ด๋ค. (c) ๊ฐ ์กฐ๊ธ ๊น๋ค๋ก์ ๋ณด์ผ ์ ์๋๋ฐ... ํต์ฌ์, ๊ฑธ์ณค์ ๊ฒฝ์ฐ ํด๋น ํ์๋ฅผ ๋ฐ๋์ ํฌํจํ๋ค๋ ๊ฒ์ด๋ค! ์ฆ, (a) ์์๋ถํฐ ์์ํ๋ค๊ณ ๊ฐ์ ํ์. ํ์์ ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ์ค, ์ฐ๋ฆฌ๋ ๋ ๋์ด๊ฐ ํฐ ๊ฒ์ ํํ๋ค. ๊ณ ๋ก (b) ์์ ์ค๋ฅธ์ชฝ์ด ์ ํ๋๋ค. ๋ค์ (b) ์์๋ ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ๋จ์ํ๊ฒ ์๊ฐํด๋ผ [์ข ๋ง๋ถ ๋ฌธ์ ] ์ฟผ๋ ํธ๋ฆฌ ๋ค์ง๊ธฐ (๋ฌธ์ ID : QUADTREE, ๋์ด๋ : ํ) ์.. ์ฟผ๋ ํธ๋ฆฌ๋ ๋๋์ ์ขํ ๋ฐ์ดํฐ๋ฅผ ๋ฉ๋ชจ๋ฆฌ ์์ ์์ถํด ์ ์ฅํ๊ธฐ ์ํด ์ฌ์ฉํ๋ ์ฌ๋ฌ ๊ธฐ๋ฒ ์ค ํ๋์ด๋ค. ์ฟผ๋ ํธ๋ฆฌ๋ ์ฃผ์ด์ง ๊ณต๊ฐ์ ํญ์ 4๊ฐ๋ก ๋ถํ ํ์ฌ ์ฌ๊ท์ ์ผ๋ก ์ ์ฅํ๋๋ฐ, ์ด๋ฒ์๋ ๊ฒ์์/ํฐ์๋ฐ์ ์๋ ๊ทธ๋ฆผ์ ์์ถํ ์์ ๋ฅผ ํ์ด ๋ณผ ๊ฒ์ด๋ค. ๐ ์ผ๋จ ๋จ์ํ ์ฌ๊ท์ ์ผ๋ก๋ง ํ๋ฉด, ์๋์ ๊ฐ์ด ํ์ด๋ณผ ์๋ ์๋ค(์ฑ ์ ๋์จ ๋ฒ์ ์ ๊ทธ ๋ค์์ ์๊ฐํ ๊ฒ์). #include #include "stdlib.h" #include u..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ์์ ํ์ ๋ฌธ์ ์ด๊ธด ํ์ง๋ง, ๋ฌธ์ ๋ฅผ ์ด์ง ๋ณํํด์ ์๊ฐํ๋ฉด ์ข๋ค. [์ข ๋ง๋ถ ๋ฌธ์ ] Synchronizing Clocks, ์๊ณ ๋ง์ถ๊ธฐ (๋ฌธ์ ID : CLOCKSYNC, ๋์ด๋ : ์ค) ์ด ๋ฌธ์ ๋ .. ์ฌ์ ํ ์์ ํ์์ผ๋ก ํ ์ ์๋ค. ๋ค๋ง, ์ฌ์ค ์ ๋ณด๋ฉด ์ค์์น๋ฅผ ๋๋ฅด๋ ์์๋ ์๊ด์ด ์๋ค๋ ๊ฒ์ ๋์น์ฑ ์ ์๋ค. ๋ฐ๋ผ์, ์ค์์น 10๊ฐ๋ฅผ ์ต๋ 3๋ฒ์ฉ ๋๋ฌ๊ฐ๋ฉด์ ๋ต์ ์ฐพ์๋๊ฐ๋ฉด ๋๋ค. ์ต๋ ์ํ์ 4^10 ์ด ๋ ๊ฒ์ด๋ค! ๐ #include #include "stdlib.h" #include using namespace std..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ์์ ํ์์ผ๋ก ๋ธ๋ก์ ๋ฎ์ด๋ณด์. ์. [์ข ๋ง๋ถ ๋ฌธ์ ] ๊ฒ์ํ ๋ฎ๊ธฐ (๋ฌธ์ ID : BOARDCOVER, ๋์ด๋ : ํ) ์ผ๋จ, ํด๋น ๋ฌธ์ ๋ ์ฌ์ค ๋ธ๋ก์ ์ด๋ป๊ฒ ๋ฎ์์ง๋ง ๊ฒฐ์ ํ๋ฉด ๋๋ต์ ์ผ๋ก ํ์ด๋ฅผ ๋ง๋ค์ด ๋ณผ ์ ์๋ค. ์ฑ ์์๋ ์์ ๊ฐ์ด ๋ฎ๋ ๋ฐฉ๋ฒ 4๊ฐ๋ฅผ ์ ์ํ๋ค. ์ฐ๋ฆฌ๋ ์ด ๋ชจ๋ธ์ ๋ฐํ์ผ๋ก ๋ฐฐ์ด์ ๋ง๋ค์ด ๋ฎ๋ ๊ฐ์ง์๋ฅผ ์ํํ๋๋ก ๋ง๋ค ๊ฒ์ด๋ค. #include #include "stdlib.h" #include using namespace std; int M, N; int board[20][20]; int ans; int blank..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ์ฌ๊ท + ์์ ํ์์ผ๋ก ํ ์ ์๋ค. [์ข ๋ง๋ถ ๋ฌธ์ ] ์ํ (๋ฌธ์ ID : PICNIC, ๋์ด๋ : ํ) ์ด๋ฒ ๋ฌธ์ ๋ ์ผ๋จ, ์์ ํ์์ผ๋ก ํ ์ ์๋ ๋ฌธ์ ์ด๊ธด ํ๋ค. ๊ฑฐ๊ธฐ์ ์ฝ๊ฐ์ ์ฌ๊ท๊ฐ ํ์ํ๋ฐ... ์ผ๋จ ์์ค ์ฝ๋๋ถํฐ ์ฒจ๋ถํด ๋ณด๊ฒ ๋ค. #include #include "stdlib.h" #include using namespace std; int N; vector pairs; int ans; void makeGroup(vector& visit, int cur, int len) { if (len == N) { ans += 1;..
ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต(์ดํ ์ข ๋ง๋ถ)์์ ์๊ฐ๋ ๋ฌธ์ ๋ฅผ ํ์ดํฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์ง์ฌ์ด์๋ผ๋ฉด, ์ง์ ๊ตฌ๋งคํ์ ์ ์ฝ์ด๋ณด์๋ ๊ฒ์ ์ถ์ฒํฉ๋๋ค! ํต์ฌ : 1. ๊ธฐ๋ณธ์ ์ผ๋ก ์์ ํ์์ผ๋ก๋, ์์ ๋ก ์ฃผ์ด์ง ์ผ์ด์ค๋ ํด๊ฒฐ ๊ฐ๋ฅํ๋ค. ํ์ง๋ง ์ ์ถํ๋ฉด Timeout ์ด ๋ฐ์ํ๋ค. 2. Timeout ํด๊ฒฐ์ ์ํด์๋... [์ข ๋ง๋ถ ๋ฌธ์ ] ๋ณด๊ธ ๊ฒ์ (๋ฌธ์ ID : BOGGLE, ๋์ด๋ : ํ) ๊ธฐ๋ณธ์ ์ผ๋ก ์์ ํ์์ผ๋ก ์ฝ๋๋ฅผ ์ง ๋ณด์. ๋ฌด์ํ๊ฒ ํ์ํ๋ค๋ฉด, ์ธ์ ํ ๊ฐ ํ์ ๋ง๋ค ์ธ์ ํ 8 ๊ฐ์ ๋ฌธ์๋ฅผ ํ์ธํด์ผ ํ๋ฏ๋ก, ์๊ฐ ๋ณต์ก๋๋ O(8^N) ์ด ๋ ๊ฒ์ด๋ค. #include #include "stdlib.h" #include #include using namespace std; char boa..