๋ฌธ์ ๋ฌธ์ ์ค๋ช 1๋ถํฐ ์ ๋ ฅ๋ฐ์ ์ซ์ n ์ฌ์ด์ ์๋ ์์์ ๊ฐ์๋ฅผ ๋ฐํํ๋ ํจ์, solution์ ๋ง๋ค์ด ๋ณด์ธ์. ์์๋ 1๊ณผ ์๊ธฐ ์์ ์ผ๋ก๋ง ๋๋์ด์ง๋ ์๋ฅผ ์๋ฏธํฉ๋๋ค. (1์ ์์๊ฐ ์๋๋๋ค.) ์ ํ ์กฐ๊ฑด n์ 2์ด์ 1000000์ดํ์ ์์ฐ์์ ๋๋ค. ์ ์ถ๋ ฅ ์ nresult 10 4 5 3 ์ ์ถ๋ ฅ ์ ์ค๋ช ์ ์ถ๋ ฅ ์ #1 1๋ถํฐ 10 ์ฌ์ด์ ์์๋ [2,3,5,7] 4๊ฐ๊ฐ ์กด์ฌํ๋ฏ๋ก 4๋ฅผ ๋ฐํ ์ ์ถ๋ ฅ ์ #2 1๋ถํฐ 5 ์ฌ์ด์ ์์๋ [2,3,5] 3๊ฐ๊ฐ ์กด์ฌํ๋ฏ๋ก 3๋ฅผ ๋ฐํ ๋ฌธ์ ํ์ด https://choi95.tistory.com/50 ๋ค์ง์ ์์ ๋ฌธ์ N๊ฐ์ ์์ฐ์๊ฐ ์ ๋ ฅ๋๋ฉด ๊ฐ ์์ฐ์๋ฅผ ๋ค์ง์ ํ ๊ทธ ๋ค์ง์ ์๊ฐ ์์์ด๋ฉด ๊ทธ ์์๋ฅผ ์ถ๋ ฅํ๊ณ ์ ํ๋ค. ์๋ฅผ ๋ค์ด 32๋ฅผ ๋ค์ง์ผ๋ฉด 23์ด๊ณ , 2..
๋ฌธ์ ๋ฌด์ธ๋์ ๊ฐํ ์ฌ๋๋ค์ ๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ด์ฉํ์ฌ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค. ๊ตฌ๋ช ๋ณดํธ๋ ์์์ ํ ๋ฒ์ ์ต๋ 2๋ช ์ฉ ๋ฐ์ ํ ์ ์๊ณ , ๋ฌด๊ฒ ์ ํ๋ ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, ์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ๊ฐ [70kg, 50kg, 80kg, 50kg]์ด๊ณ ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ์ด 100kg์ด๋ผ๋ฉด 2๋ฒ์งธ ์ฌ๋๊ณผ 4๋ฒ์งธ ์ฌ๋์ ๊ฐ์ด ํ ์ ์์ง๋ง 1๋ฒ์งธ ์ฌ๋๊ณผ 3๋ฒ์งธ ์ฌ๋์ ๋ฌด๊ฒ์ ํฉ์ 150kg์ด๋ฏ๋ก ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ์ ์ด๊ณผํ์ฌ ๊ฐ์ด ํ ์ ์์ต๋๋ค. ๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ต๋ํ ์ ๊ฒ ์ฌ์ฉํ์ฌ ๋ชจ๋ ์ฌ๋์ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค. ์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ๋ฅผ ๋ด์ ๋ฐฐ์ด people๊ณผ ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ limit๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ฌ๋์ ๊ตฌ์ถํ๊ธฐ ์ํด ํ์ํ ๊ตฌ๋ช ๋ณดํธ ๊ฐ์์ ์ต์๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ..
๋ฌธ์ ๋ ์๋ฅผ ์ ๋ ฅ๋ฐ์ ๋ ์์ ์ต๋๊ณต์ฝ์์ ์ต์๊ณต๋ฐฐ์๋ฅผ ๋ฐํํ๋ ํจ์, solution์ ์์ฑํด ๋ณด์ธ์. ๋ฐฐ์ด์ ๋งจ ์์ ์ต๋๊ณต์ฝ์, ๊ทธ๋ค์ ์ต์๊ณต๋ฐฐ์๋ฅผ ๋ฃ์ด ๋ฐํํ๋ฉด ๋ฉ๋๋ค. ์๋ฅผ ๋ค์ด ๋ ์ 3, 12์ ์ต๋๊ณต์ฝ์๋ 3, ์ต์๊ณต๋ฐฐ์๋ 12์ด๋ฏ๋ก solution(3, 12)๋ [3, 12]๋ฅผ ๋ฐํํด์ผ ํฉ๋๋ค.์ ํ ์ฌํญ ๋ ์๋ 1์ด์ 1000000์ดํ์ ์์ฐ์์ ๋๋ค. ์ ์ถ๋ ฅ ์ nmreturn 3 12 [3, 12] 2 5 [1, 10] ์ ์ถ๋ ฅ ์ ์ค๋ช ์ ์ถ๋ ฅ ์ #1 ์์ ์ค๋ช ๊ณผ ๊ฐ์ต๋๋ค. ์ ์ถ๋ ฅ ์ #2 ์์ฐ์ 2์ 5์ ์ต๋๊ณต์ฝ์๋ 1, ์ต์๊ณต๋ฐฐ์๋ 10์ด๋ฏ๋ก [1, 10]์ ๋ฆฌํดํด์ผ ํฉ๋๋ค. ๋ฌธ์ ํ์ด ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ(Euclidean-Algorithm) ๋ ์์ ์ต๋๊ณต์ฝ์(GCD)๋ฅผ ๊ตฌํ๋ ์..
๋ฌธ์ ๋ฐ์ดํฐ ์ฒ๋ฆฌ ์ ๋ฌธ๊ฐ๊ฐ ๋๊ณ ์ถ์ "์ดํผ์น"๋ ๋ฌธ์์ด์ ์์ถํ๋ ๋ฐฉ๋ฒ์ ๋ํด ๊ณต๋ถ๋ฅผ ํ๊ณ ์์ต๋๋ค. ์ต๊ทผ์ ๋๋์ ๋ฐ์ดํฐ ์ฒ๋ฆฌ๋ฅผ ์ํ ๊ฐ๋จํ ๋น์์ค ์์ถ ๋ฐฉ๋ฒ์ ๋ํด ๊ณต๋ถ๋ฅผ ํ๊ณ ์๋๋ฐ, ๋ฌธ์์ด์์ ๊ฐ์ ๊ฐ์ด ์ฐ์ํด์ ๋ํ๋๋ ๊ฒ์ ๊ทธ ๋ฌธ์์ ๊ฐ์์ ๋ฐ๋ณต๋๋ ๊ฐ์ผ๋ก ํํํ์ฌ ๋ ์งง์ ๋ฌธ์์ด๋ก ์ค์ฌ์ ํํํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ณต๋ถํ๊ณ ์์ต๋๋ค. ๊ฐ๋จํ ์๋ก "aabbaccc"์ ๊ฒฝ์ฐ "2a2ba3c"(๋ฌธ์๊ฐ ๋ฐ๋ณต๋์ง ์์ ํ๋ฒ๋ง ๋ํ๋ ๊ฒฝ์ฐ 1์ ์๋ตํจ)์ ๊ฐ์ด ํํํ ์ ์๋๋ฐ, ์ด๋ฌํ ๋ฐฉ์์ ๋ฐ๋ณต๋๋ ๋ฌธ์๊ฐ ์ ์ ๊ฒฝ์ฐ ์์ถ๋ฅ ์ด ๋ฎ๋ค๋ ๋จ์ ์ด ์์ต๋๋ค. ์๋ฅผ ๋ค๋ฉด, "abcabcdede"์ ๊ฐ์ ๋ฌธ์์ด์ ์ ํ ์์ถ๋์ง ์์ต๋๋ค. "์ดํผ์น"๋ ์ด๋ฌํ ๋จ์ ์ ํด๊ฒฐํ๊ธฐ ์ํด ๋ฌธ์์ด์ 1๊ฐ ์ด์์ ๋จ์๋ก ์๋ผ์ ..
๋ฌธ์ ๋ค์ค๋ ํ์ ํ๋ก๋๊ฐ ๋น์๊ธ์ ์จ๊ฒจ๋๋ ์ฅ์๋ฅผ ์๋ ค์ค ๋น๋ฐ์ง๋๋ฅผ ์์ ๋ฃ์๋ค. ๊ทธ๋ฐ๋ฐ ์ด ๋น๋ฐ์ง๋๋ ์ซ์๋ก ์ํธํ๋์ด ์์ด ์์น๋ฅผ ํ์ธํ๊ธฐ ์ํด์๋ ์ํธ๋ฅผ ํด๋ ํด์ผ ํ๋ค. ๋คํํ ์ง๋ ์ํธ๋ฅผ ํด๋ ํ ๋ฐฉ๋ฒ์ ์ ์ด๋์ ๋ฉ๋ชจ๋ ํจ๊ป ๋ฐ๊ฒฌํ๋ค. ์ง๋๋ ํ ๋ณ์ ๊ธธ์ด๊ฐ n์ธ ์ ์ฌ๊ฐํ ๋ฐฐ์ด ํํ๋ก, ๊ฐ ์นธ์ "๊ณต๋ฐฑ"(" ") ๋๋ "๋ฒฝ"("#") ๋ ์ข ๋ฅ๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ์ ์ฒด ์ง๋๋ ๋ ์ฅ์ ์ง๋๋ฅผ ๊ฒน์ณ์ ์ป์ ์ ์๋ค. ๊ฐ๊ฐ "์ง๋ 1"๊ณผ "์ง๋ 2"๋ผ๊ณ ํ์. ์ง๋ 1 ๋๋ ์ง๋ 2 ์ค ์ด๋ ํ๋๋ผ๋ ๋ฒฝ์ธ ๋ถ๋ถ์ ์ ์ฒด ์ง๋์์๋ ๋ฒฝ์ด๋ค. ์ง๋ 1๊ณผ ์ง๋ 2์์ ๋ชจ๋ ๊ณต๋ฐฑ์ธ ๋ถ๋ถ์ ์ ์ฒด ์ง๋์์๋ ๊ณต๋ฐฑ์ด๋ค. "์ง๋ 1"๊ณผ "์ง๋ 2"๋ ๊ฐ๊ฐ ์ ์ ๋ฐฐ์ด๋ก ์ํธํ๋์ด ์๋ค. ์ํธํ๋ ๋ฐฐ์ด์ ์ง๋์ ๊ฐ ๊ฐ๋ก์ค์..
๋ฌธ์ https://www.acmicpc.net/problem/1874 1874๋ฒ: ์คํ ์์ด 1๋ถํฐ n๊น์ง์ ์์ ๋ํด ์ฐจ๋ก๋ก [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] ์ฐ์ฐ์ ์ํํ๋ฉด ์์ด [4, 3, 6, 8, 7, 5, 2, 1]์ ์ป์ ์ ์๋ค. www.acmicpc.net ๋ฌธ์ ํ์ด ์ฃผ์ด์ง ์ ์๊ฐ์ด 0์ผ๋ก ์ด๊ธฐํ ๋ max๋ณด๋ค ํด ๊ฒฝ์ฐ์ ํด๋น ์ ์๊ฐ๊น์ง push ์ฐ์ฐ ํด๋น ์ ์๊ฐ๊น์ง push๋ stack ๋ฐฐ์ด ๋ด์์ ๋ง์ง๋ง ์ธ๋ฑ์ค ์์์ธ ์ฃผ์ด์ง ์ ์๊ฐ์ pop ์ฐ์ฐ max๊ฐ์ ์ฃผ์ด์ง ์ ์๊ฐ์ผ๋ก ์ด๊ธฐํ ์ฃผ์ด์ง ์ ์๊ฐ์ด ์ด์ ์ ์๊ฐ์ผ๋ก ์ด๊ธฐํ ๋ max๊ฐ๋ณด๋ค ์์ ๊ฒฝ์ฐ์ ํด๋น ์ ์๊ฐ๊น..
๋ฌธ์ ์นด์นด์คํก ๊ฒ์๋ณ์ ํ๋ฐ๊ธฐ ์ ๊ท ์๋น์ค๋ก ๋คํธ ๊ฒ์์ ์ถ์ํ๊ธฐ๋ก ํ๋ค. ๋คํธ ๊ฒ์์ ๋คํธํ์ ๋คํธ๋ฅผ ์ธ ์ฐจ๋ก ๋์ ธ ๊ทธ ์ ์์ ํฉ๊ณ๋ก ์ค๋ ฅ์ ๊ฒจ๋ฃจ๋ ๊ฒ์์ผ๋ก, ๋ชจ๋๊ฐ ๊ฐ๋จํ ์ฆ๊ธธ ์ ์๋ค. ๊ฐ ์ ์ฌํ ๋ฌด์ง๋ ์ฝ๋ฉ ์ค๋ ฅ์ ์ธ์ ๋ฐ์ ๊ฒ์์ ํต์ฌ ๋ถ๋ถ์ธ ์ ์ ๊ณ์ฐ ๋ก์ง์ ๋งก๊ฒ ๋์๋ค. ๋คํธ ๊ฒ์์ ์ ์ ๊ณ์ฐ ๋ก์ง์ ์๋์ ๊ฐ๋ค. ๋คํธ ๊ฒ์์ ์ด 3๋ฒ์ ๊ธฐํ๋ก ๊ตฌ์ฑ๋๋ค. ๊ฐ ๊ธฐํ๋ง๋ค ์ป์ ์ ์๋ ์ ์๋ 0์ ์์ 10์ ๊น์ง์ด๋ค. ์ ์์ ํจ๊ป Single(S), Double(D), Triple(T) ์์ญ์ด ์กด์ฌํ๊ณ ๊ฐ ์์ญ ๋น์ฒจ ์ ์ ์์์ 1์ ๊ณฑ, 2์ ๊ณฑ, 3์ ๊ณฑ (์ ์1 , ์ ์2 , ์ ์3 )์ผ๋ก ๊ณ์ฐ๋๋ค. ์ต์ ์ผ๋ก ์คํ์(*) , ์์ฐจ์(#)์ด ์กด์ฌํ๋ฉฐ ์คํ์(*) ๋น์ฒจ ์ ํด๋น ์ ์์ ๋ฐ๋ก ์ ์ ์ป์ ..
๋ฌธ์ https://www.acmicpc.net/problem/9012 9012๋ฒ: ๊ดํธ ๊ดํธ ๋ฌธ์์ด(Parenthesis String, PS)์ ๋ ๊ฐ์ ๊ดํธ ๊ธฐํธ์ธ ‘(’ ์ ‘)’ ๋ง์ผ๋ก ๊ตฌ์ฑ๋์ด ์๋ ๋ฌธ์์ด์ด๋ค. ๊ทธ ์ค์์ ๊ดํธ์ ๋ชจ์์ด ๋ฐ๋ฅด๊ฒ ๊ตฌ์ฑ๋ ๋ฌธ์์ด์ ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด(Valid PS, VPS)์ด๋ผ๊ณ www.acmicpc.net ๋ฌธ์ ํ์ด https://choi95.tistory.com/74?category=881084 [์คํ]์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์ ๊ดํธ๊ฐ ์ ๋ ฅ๋๋ฉด ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด๋ฉด "YES", ์ฌ๋ฐ๋ฅด์ง ์์ผ๋ฉด "NO"๋ฅผ ์ถ๋ ฅํฉ๋๋ค.(())() ์ด๊ฒ์ ๊ดํธ์ ์์ด ์ฌ๋ฐ๋ฅด๊ฒ ์์นํ๋ ๊ฑฐ์ง๋ง, (()()))) ์ ์ฌ๋ฐ๋ฅธ ๊ดํธ๊ฐ ์๋๋ค. ๋ฌธ์ ํ์ด ์คํ ์คํ(stack) choi95.tistory.co..