๐งฉ Problem Solving/[๋ฐฑ์ค]
2839๋ฒ: ์คํ ๋ฐฐ๋ฌ ์๊ทผ์ด๋ ์์ฆ ์คํ๊ณต์ฅ์์ ์คํ์ ๋ฐฐ๋ฌํ๊ณ ์๋ค. ์๊ทผ์ด๋ ์ง๊ธ ์ฌํ๊ฐ๊ฒ์ ์คํ์ ์ ํํ๊ฒ Nํฌ๋ก๊ทธ๋จ์ ๋ฐฐ๋ฌํด์ผ ํ๋ค. ์คํ๊ณต์ฅ์์ ๋ง๋๋ ์คํ์ ๋ด์ง์ ๋ด๊ฒจ์ ธ ์๋ค. ๋ด์ง๋ 3ํฌ๋ก๊ทธ www.acmicpc.net ์คํ Nํฌ๋ก๊ทธ๋จ์ ์ฃผ๊ณ ์ด๊ฑธ 5ํฌ๋ก๊ทธ๋จ, 3ํฌ๋ก๊ทธ๋จ ๋ด์ง๋ก ๊ฐ์ฅ ์ ์ ๊ฐ์๋ก ๋๋๋ ๋ฌธ์ . ์ฒ์์๋ ์ํ์ผ๋ก ํด๊ฒฐํ๋ ค๋ค๊ฐ "๋์ " ๋ฌธ์ ๊ฐ ์๊ฐ๋์ DP๋ก ํด๊ฒฐํ๋ค. ์์ด๋์ด nํฌ๋ก๊ทธ๋จ์ (n - 3) + 3 ๋๋ (n - 5) + 5๋ก ์๊ฐํ ์ ์๋ค. ๋ฐ๋ผ์ nํฌ๋ก๊ทธ๋จ์ ๋ด์ง ๊ฐ์๋ n - 3๊ณผ n - 5 ํฌ๋ก๊ทธ๋จ ๋ด์ง ๊ฐ์ ์ค ์์ ๊ฑฐ(min) + 1์ด ๋๋ค. ์ด ์์ด๋์ด๋ก ํด๊ฒฐํ๋ ค๋ฉด n - 3๊ณผ n - 5์ ๊ฐ์ ์ ๋ณด๋ฅผ ์ ์ฅํด ๋๋ค๊ฐ ์ฌ์ฌ์ฉ์ด ํ์ํ๋ค. 3 ~ nํฌ๋ก..
๐งฉ Problem Solving/[๋ฐฑ์ค]
2447๋ฒ: ๋ณ ์ฐ๊ธฐ - 10 ์ฌ๊ท์ ์ธ ํจํด์ผ๋ก ๋ณ์ ์ฐ์ด ๋ณด์. N์ด 3์ ๊ฑฐ๋ญ์ ๊ณฑ(3, 9, 27, ...)์ด๋ผ๊ณ ํ ๋, ํฌ๊ธฐ N์ ํจํด์ N×N ์ ์ฌ๊ฐํ ๋ชจ์์ด๋ค. ํฌ๊ธฐ 3์ ํจํด์ ๊ฐ์ด๋ฐ์ ๊ณต๋ฐฑ์ด ์๊ณ , ๊ฐ์ด๋ฐ๋ฅผ ์ ์ธํ ๋ชจ๋ ์นธ์ ๋ณ์ด www.acmicpc.net ๊ฑฐ์ 1๋
์ ์ ํ์๋ ๋ฌธ์ . ์ง์ง ์๋ฌด๋ฐ ๊ณ๊ธฐ ์์ด ๊ทธ๋ฅ ๋ฌ๊ธ์์ด ๋ค์ ์๊ฐ๋์ ํ์ด๋ดค๋ค. ๋คํํ ํด๊ฒฐ ์ด ๋ฌธ์ ๋ ์ฌ๊ท์ ํน์ง์ ์ ์ดํดํ๋ฉด ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ๋ค. ๊ด์ฐฎ์ ๋ฌธ์ ์ธ ๊ฑฐ ๊ฐ๋ค. ๊ผญ ํ๊ณ ๋์ ์์ ์ ๊ฒ์ผ๋ก ์ฒดํํ์. ์์ด๋์ด ์ฌ๊ณ ๋ฅผ ํ์ด๊ฐ๋ ๊ฑฐ๋ผ ์ข ์ถ์์ ์ผ ์ ์๋ค. ์ผ๋จ ์ฒซ ๋ฒ์งธ N = 3์ธ ๊ฒฝ์ฐ๋ ๋ค์๊ณผ ๊ฐ๋ค. *** * * *** ๊ทธ๋ฆฌ๊ณ N = 9์ธ ๊ฒฝ์ฐ๋ ๋ค์๊ณผ ๊ฐ๋ค. ์ฌ๊ธฐ์ ํจํด์ ๋๋ ๋ณด๋ฉด ํฌ๊ฒ Aํํธ(๋นจ๊ฐ์..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/28018 28018๋ฒ: ์๊ฐ์ด ๊ฒน์น ๊น? ๋๊ธ์ ๋ฌ์์ค ํ์ ์ $N$์ด ์ฃผ์ด์ง๋ค. $(1\leq N\leq 100\,000)$ ๋ค์ $N$๊ฐ ์ค์๋ ๊ฐ ํ์์ ์ข์ ๋ฐฐ์ ์๊ฐ $S$์ ์ข
๋ฃ ์๊ฐ $E$๊ฐ ์ฃผ์ด์ง๋ค. $(1\leq S\leq E\leq 1\,000\,000)$ ๋ค์ ์ค์๋ ํน์ ํ ์๊ฐ์ ๊ฐ์ www.acmicpc.net ๋ํ์์ ํด๊ฒฐ ๋ชปํ๊ณ ๋๋๊ณ ํด๊ฒฐํ ๋ฌธ์ . ์ฒ์ ๋ฃ๋ ์๊ณ ๋ฆฌ์ฆ์ด์ด์ ์ ๊ธฐํ๋ค.(๋์ ํฉ ์๊ณ ๋ฆฌ์ฆ ๊ฐ๋ค) ์์ง๋ ๋ชจ๋ฅด๋๊ฒ ๋ง์๊ฑฐ ๊ฐ๋ค, ๋ฐฐ์์๋ ๋์ด ์๋ ๊ฑฐ ๊ฐ๋ค. ์์ด๋์ด ๋ฌธ์ ๋ฅผ ๋ณด๊ณ ์๊ฐ์ ํ์ ๊ณ ๋ คํ์ง์์ผ๋ฉด ์ ๋ง ์ฌ์ด ๋์ด๋๋ค. ํ์ง๋ง ์
๋ ฅ๊ฐ์ด ํฌ๊ธฐ ๋๋ฌธ์ ์๊ฐ ๊ณ ๋ฏผ์ ํด๋ด์ผ ๋๋ค. ์ด ์์ด๋์ด๋ฅผ ์ฝ๊ฒ ๋งํ๋ฉด, ๋ค..
๐งฉ Problem Solving/[SW Expert Academy]
SW Expert Academy SW ํ๋ก๊ทธ๋๋ฐ ์ญ๋ ๊ฐํ์ ๋์์ด ๋๋ ๋ค์ํ ํ์ต ์ปจํ
์ธ ๋ฅผ ํ์ธํ์ธ์! swexpertacademy.com ์ฒ์ ํ์ด๋ณธ SW Expert Academy. ์์ง ํ ๋ฌธ์ ๋ง ํ์ด๋ด์ ์ ๋ชจ๋ฅด๊ฒ ๋ค. ๋ช ๋ฌธ์ ํ์ด๋ณด๋ฉด ๋๋์ ์ ๊ฑฐ ๊ฐ๋ค. ๋ฌธ์ ํ์ด์ง์ input.txt๋ฅผ ๋ณด๊ณ ํ์ผ ์
์ถ๋ ฅ์ ํด์ผ ํ๋ ํ๋๋ฐ, ๊ทธ๋ฅ ํ์ ๋ฌธ์ ํ๋ฏ ํ๋ฉด ๋๋ค. ๊ทผ๋ฐ ๊ถ๊ธํ ๊ฒ input์ด ์ ๋ถ ์ฃผ์ด์ง๋ฉด, ํ๋์ฝ๋ฉ์ผ๋ก ์ ์ถํด๋ ์ ๋ต์ธ๊ฐ? ๋ชจ๋ฅด๊ฒ ๋ค. ๊ทธ๋ฆฌ๊ณ ์ด ๋ฌธ์ ๋ง ๊ทธ๋ฐ์ง ๋ชจ๋ฅด๊ฒ ๋๋ฐ, ์ถ๋ ฅ์ด ํน์ดํ๋ค. #1 1231, #2 5343, #3 1233... ์ด๋ฐ ์์ผ๋ก ์ ์ถ ํ๊ฒฝ๋ ์ฒ์ ๋ด์ ์ด์ง ๋๊ฐ ์ ์งํ๋๋ฐ, ๊ทธ๋ฅ ์๋๋๋ก ํ๋ฉด ๋๋ค. ์์ด๋์ด ์ฝ๋ ๊ธธ์ด๋ฅผ ๋ณด๋ฉด ์๊ฒ ์ง๋ง ๋งค์ฐ ๊ฐ๋จํ๋ค. ์คํ..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/28303 28303๋ฒ: ์์ ์์ 1์ ๊ฒฝ์ฐ N๊ทน์ด 3๋ฒ ์นธ์ ๋์ด๊ณ S๊ทน์ด 5๋ฒ ์นธ์ ๋์ด๋๋ก ์์์ ์ค์นํ ๋ 1๋ฒ ํ์์ผ๋ก $a_3=22$์ ์๋์ง๊ฐ ์ถฉ์ ๋๋ฉฐ, 2๋ฒ ํ์์ผ๋ก $a_5=4$์ ์๋์ง๊ฐ ์๋ชจ๋๊ณ , 3๋ฒ ํ์์ผ๋ก $(5-3)\times 2=4$ www.acmicpc.net N์ ์ต๋๊ฐ์ด 500,000์ด๋ค. ์๊ฐ์ ํ์ 2์ด๋ ๋์ง๋ง, N**2 ๊ฐ์ ๊ฑด ์ ๋ ์ ๋๋ค. ์ด๋ฐ ๊ฑธ ๊ณ ๋ คํด์ ์ฒ์์๋ DP, ๊ทธ๋ฆฌ๋, ๋์ ํฉ, ํฌํฌ์ธํฐ ๋ฑ๋ฑ ์๊ฐํ์๋๋ฐ 1์๊ฐ ์ ๋ ์์ด๋์ด๋ ์ ๋์๋ค. ๊ฒฐ๊ตญ ์๊ณ ๋ฆฌ์ฆ ๋ถ๋ฅ๋ฅผ ํ์ธํ๋ค. ๋์ ํฉ ์ธ๊ฑธ ํ์ธํ๊ณ ์ต๋ํ ๋์ ํฉ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ๋ ค๊ณ ํ๋ค. ์ฝ๋ ์์ฑ ์ค๊ฐ์ ๋ด๊ฐ ์ํ๋ ๋ก์ง์ ๊ตฌํํ๊ธฐ ์ํด..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/28286 28286๋ฒ: ์ฌ์ฑ์ ์ ๊ธฐ๋ค๋ฆฌ๋ ์ค UCPC๊ณ ๋ฑํ๊ต์ ๋ค๋๋ ๋ฏผ๊ท๋ ์ต๊ทผ์ ๊ธฐ๋ง๊ณ ์ฌ๋ฅผ ์น๊ฒ ๋์๋ค. ๊ธฐ๋ง๊ณ ์ฌ๋ $N$๋ฌธ์ ๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ๊ฐ ๋ฌธ์ ๋ ๋ณด๊ธฐ๊ฐ 1 ์ด์ 5 ์ดํ์ ์ ์๋ก ์ด๋ฃจ์ด์ง ๊ฐ๊ด์ ๋ฌธ์ ์ด๋ค. ์๊ฐ์ด ์ง๋ ํ๊ต์์ www.acmicpc.net ์ฒ์ ๋ฌธ์ ๋ฅผ ์ฝ์์ ๋๋ ์๊ฐ์ ์ด๋ป๊ฒ ์ค์ผ๊น ๊ณ ๋ฏผํ๋๋ฐ, ์
๋ ฅ๊ฐ์ด ๋งค์ฐ ์๋ค.(max(N) = 20, max(K) = 3) ๋ฌด๋ํ ๋ฌธ์ . ๋ฐฑํธ๋ํน์ ์ฌ์ฉํด์ ์ต๋ ๊ฐ์๋ฅผ ์ฐพ์์ค๋ค. ์์ด๋์ด 1. pull: ๋ฒํธ๋ค์ ์ผ์ชฝ์ผ๋ก ๋น๊ธฐ๋ ๊ธฐ๋ฅ. rotate๋ฅผ ์จ์ ๊ตฌํํ๋ค. for๋ฌธ์ผ๋ก ๊ตฌํํด๋ ๋๋ค. 2. push: ๋ฒํธ๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ๋ฏธ๋ ๊ธฐ๋ฅ. pull๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก rotate๋ฅผ ์จ..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/28298 28298๋ฒ: ๋ ํํ ํ์ผ ์์น ๋ฌธ์ ์ฒซ์งธ ์ค์ ์ธ ์ ์ $N$, $M$, $K$๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. $(1\le N,M,K\le 500;$ $N,M$์ $K$์ ๋ฐฐ์์ด๋ค$)$ ๋ค์ $N$๊ฐ์ ์ค์๋ ํ์ผ์ $i$ํ ์์ ๋ฐฐ์น๋ฅผ ์๋ฏธํ๋ ๊ธธ์ด $M$์ ๋ฌธ์์ด $d_i$๊ฐ ์ฃผ์ด์ง๋ค. www.acmicpc.net ์๊ฐ ์ด๊ณผ๊ฐ ์๊ธด ๋ฌธ์ . ์ด๋ฒ์ ์
๋ ฅ๊ฐ ์ ํ์ ๋ณด๊ณ ์๊ฐ์ ๋ง๊ฒ ๋ก์ง์ ์งฐ๋ค๊ณ ์๊ฐํ๋๋ฐ ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค. ๋ก์ง์ ์กฐ๊ธ ์์ ํ๋๊น ํต๊ณผํ๋ค. ์ ๊ทธ๋ฐ์ง ์๊ฐํด ๋ณด๋ ์์ธ์ ์ฐพ์ ์ ์์๋ค. ์ค๊ฐ์ ๋ฆฌ์คํธ์์ ๊ฐ์๊ฐ ๊ฐ์ฅ ๋ง์ ์์๋ฅผ ์ถ๋ ฅํ๋ ๋ฉ์๋๊ฐ ํ์ํ๋ค. ๋ง์ ๋ฐฉ๋ฒ์ด ์์ง๋ง ๋๋ ์ฝ๋๋ฅผ ๊ฐ๊ฒฐํ๊ฒ ์์ฑํ๊ณ ์ถ์ด ..
๐งฉ Problem Solving/[๋ฐฑ์ค]
https://www.acmicpc.net/problem/28250 28250๋ฒ: ์ด๋ธ, ํ์์ผ ๊ทธ๋ฆฌ๊ณ ํธ๋ฅธ MEX์ ์๋ด ์ฒซ์งธ ์ค์ ์ ์ $N$์ด ์ฃผ์ด์ง๋ค. ($2 \le N \le 200\,000$) ๋์งธ ์ค์ $N$๊ฐ์ ์ ์ $A_1, A_2, \dots, A_N$์ด ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. ($0 \le A_i \le 100\,000$) www.acmicpc.net ์์ด๋์ด https://aia1235.tistory.com/75 [๋ฐฑ์ค] 28250 ์ด๋ธ, ํ์์ผ ๊ทธ๋ฆฌ๊ณ ํธ๋ฅธ MEX์ ์๋ด (python ํ์ด์ฌ) https://www.acmicpc.net/problem/28250 28250๋ฒ: ์ด๋ธ, ํ์์ผ ๊ทธ๋ฆฌ๊ณ ํธ๋ฅธ MEX์ ์๋ด ์ฒซ์งธ ์ค์ ์ ์ $N$์ด ์ฃผ์ด์ง๋ค. ($2 \le N \le ..