ํ์ด์ฌ(8)
-
๋ฐฑ์ค 2011 ํ์ด์ฌ
https://www.acmicpc.net/problem/2011 2011๋ฒ: ์ํธ์ฝ๋ ๋์ฌ ์ ์๋ ํด์์ ๊ฐ์ง์๋ฅผ ๊ตฌํ์์ค. ์ ๋ต์ด ๋งค์ฐ ํด ์ ์์ผ๋ฏ๋ก, 1000000์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค. ์ํธ๊ฐ ์๋ชป๋์ด ์ํธ๋ฅผ ํด์ํ ์ ์๋ ๊ฒฝ์ฐ์๋ 0์ ์ถ๋ ฅํ๋ค. www.acmicpc.net 2011๋ฒ์ Dynamic Programming ๋ฌธ์ ์ ๋๋ค. DP ๋ฌธ์ ๋ ํ ๋ฒ ์๊ฐ์ด ์ ๋๋ฉด ์๋ฌด๋ฆฌ ์์ ๊ธธ๊ฒ ์ฐ๋ฉด์ ๋ ธ๊ฐ๋ค๋ฅผ ํด๋ณด๊ณ ๊ท์น์ ์ฐพ์ผ๋ ค๊ณ ํด๋ ์๋ชป ์ฐพ๊ฒ ๋๊ฑฐ๋, ์์ ๋ชป ์ฐพ๊ฒ ๋๋ ๊ฒฝ์ฐ๊ฐ ๋ง์ ๊ฒ ๊ฐ์ต๋๋ค(๋ฌผ๋ก ์ ํ์ ). DP ๋ฌธ์ ๋ฅผ ๋ ํ์ด๋ณด๊ณ , ์์ ์ ํ์๋ ๊ฒ๋ค๋ ๋ค์ ํ์ด๋ณด๋ฉด ๋ฐ์ดํฐ๊ฐ ์์ด๋ฉด์ ์ข ๋ ๋น ๋ฅด๊ฒ ๊ท์น์ ์ฐพ๊ณ ์์ ์ฐพ์ ์ ์์ ๊ฒ ๊ฐ์ง๋ง, ์์ง์ ๊ทธ๋ฐ ๊ฒฝ์ง์๋ ๋ค๋ค๋ฅด์ง ๋ชปํ ..
2021.07.31 -
๋ฐฑ์ค 1924 ํ์ด์ฌ
https://www.acmicpc.net/problem/1924 1924๋ฒ: 2007๋ ์ฒซ์งธ ์ค์ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ x(1 ≤ x ≤ 12)์ y(1 ≤ y ≤ 31)์ด ์ฃผ์ด์ง๋ค. ์ฐธ๊ณ ๋ก 2007๋ ์๋ 1, 3, 5, 7, 8, 10, 12์์ 31์ผ๊น์ง, 4, 6, 9, 11์์ 30์ผ๊น์ง, 2์์ 28์ผ๊น์ง ์๋ค. www.acmicpc.net ๊ตฌํด์ผ ํ๋ ๋ฐ๋ ๊ฐ๋จํ๋ค! 2007๋ x์ y์ผ์ด ๋ฌด์จ ๋ ์ง์ธ์ง ๊ตฌํ๋ฉด ๋๋ค. 2007๋ 1์ 1์ผ์ ์์์ผ์ด๋ค. ๋๋ ์ด ๋ฌธ์ ๋ฅผ ์ด๋ป๊ฒ ์ ๊ทผํด์ผ ๊ฐ๋จํ๊ฒ ํ ์ ์์์ง ๊ณ ๋ฏผ์ ๊ฝค ํ ๊ฒ ๊ฐ๋ค. ์ฒ์์ ๊ณ ๋ฏผํ ๊ฒ์ ์๋ณ๋ก 31์ผ์ด๊ฑฐ๋, 30์ผ์ด๊ฑฐ๋, 28์ผ์ด ๋๋๋ฐ ์ด๊ฑธ ์ด๋ป๊ฒ ๊ณ์ฐํด์ผ ๊ทธ ๋ค์ ์์ ์์ ์์ผ์ ์ ์ ์์๊น, ํ๋ ๊ฒ์ด์๋ค. ๊ฐ์ ๋ฌ ..
2021.06.29 -
๋ฐฑ์ค 1946 ํ์ด์ฌ
www.acmicpc.net/problem/1946 1946๋ฒ: ์ ์ ์ฌ์ ์ฒซ์งธ ์ค์๋ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T(1 ≤ T ≤ 20)๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์ ์ง์์์ ์ซ์ N(1 ≤ N ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ ์ค์๋ ๊ฐ๊ฐ์ ์ง์์์ ์๋ฅ์ฌ์ฌ ์ฑ www.acmicpc.net ์ด ๋ฌธ์ ๋ ์ฐ์ ์ดํด๊ฐ ์ค์ํด ๋ณด์ธ๋ค. ์ฒ์์ ๋ฌธ์ ์์ฒด๋ฅผ ์ดํด ๋ชป ํด์ ์ด๋ป๊ฒ ์ ๊ทผํด์ผ ์์ ์ ๋ต์ด ๋์ค๋์ง๋ ๊ธด๊ฐ๋ฏผ๊ฐํด์.. ์ฒ์์ ์กฐ๊ธ ์๋ํ๋ค๊ฐ ๋ฐฉ์นํด ๋์๋ค๊ฐ ๋ค์ ๊บผ๋ด์ ํ์๋ค. 1946 ์ง๋ฌธ์์ ์ด๋ค ๋ถ์ด ์ฝ๋ฉํธ์ ๋๋ฌด ์ ์ค๋ช ํด์ฃผ์ ์ ์ค๋ช ์ ๊ทธ๋๋ก ๊ฐ์ ธ์๋ค. ์ง์์๊ฐ ๋ชจ๋ ํ ์ฅ์์ ๋ชจ์๋ค๊ณ ์๊ฐํด ๋ณผ๊ฒ์. ๊ทธ ์ค์ ํ ์ง์์์ ์ ์ฅ์ด ๋์ด, ๋ค๋ฅธ ์ง์์๋ค์ ๋ฉด์ , ์๋ฅ ์ ์..
2021.05.04 -
๋ฐฑ์ค 1476 ํ์ด์ฌ
www.acmicpc.net/problem/1476 1476๋ฒ: ๋ ์ง ๊ณ์ฐ ์ค๊ท๊ฐ ์ฌ๋ ๋๋ผ๋ ์ฐ๋ฆฌ๊ฐ ์ฌ์ฉํ๋ ์ฐ๋์ ๋ค๋ฅธ ๋ฐฉ์์ ์ด์ฉํ๋ค. ์ค๊ท๊ฐ ์ฌ๋ ๋๋ผ์์๋ ์ 3๊ฐ๋ฅผ ์ด์ฉํด์ ์ฐ๋๋ฅผ ๋ํ๋ธ๋ค. ๊ฐ๊ฐ์ ์๋ ์ง๊ตฌ, ํ์, ๊ทธ๋ฆฌ๊ณ ๋ฌ์ ๋ํ๋ธ๋ค. ์ง๊ตฌ๋ฅผ ๋ํ www.acmicpc.net ์ํ ๊ธฐ๊ฐ์ ๊ณต๋ถ๋ ํ๊ธฐ ์ซ๊ณ ํด์.. ๊ฐ๋จํ๊ฒ ํ ๋ฌธ์ ํ์ด๋ณด๋ ค๊ณ ํ๋๋ฐ ์ญ์๋ ์ํ..ํด๊ฒฐ๋ ฅ์ด ๋ถ์กฑํด์ ๊ทธ๋ ๊ฒ ์ด๋ ค์ด ๋ฌธ์ ๋ ์๋ ๊ฒ ๊ฐ์๋๋ฐ ์์ ์๊ฐ๋ณด๋ค ์ค๋ ๊ฑธ๋ ธ๋ค. ๋์ค์ ์ด๋์ ์ฝ๋ฉ ํ ์คํธ๋ ์ด๋ป๊ฒ ๋ณด๋..ํ๋ ๋ง์์ด.. ์ฒ์์๋ ๊ต์ฅํ ์์ฒญ๋ ๊ท์น์ด ์๋ค๊ณ ์๊ฐํ๊ณ ์ด๋ ต๊ฒ ์๊ฐํ๋ค. ์ฐ์ 15, 28, 19 ๊ธฐ์ค์ผ๋ก ๊ณต๋ฐฐ์๋ฅผ ๋ง๋ค์ด๋ด๋ ๊ฒ ๊ฐ์๋ฐ.. ๋๋.. ํ๋ฉฐ ๋ฉ๋ชจ์ฅ์ ๊ณ์ ์ธ ์๋ฆฌ์ฉ ์จ๋ดค๋ค..ใ ...
2021.04.07 -
๋ฐฑ์ค 1021๋ฒ ํ์ด์ฌ
www.acmicpc.net/problem/1021 1021๋ฒ: ํ์ ํ๋ ํ ์ฒซ์งธ ์ค์ ํ์ ํฌ๊ธฐ N๊ณผ ๋ฝ์๋ด๋ ค๊ณ ํ๋ ์์ ๊ฐ์ M์ด ์ฃผ์ด์ง๋ค. N์ 50๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๊ณ , M์ N๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ๋์งธ ์ค์๋ ์ง๋ฏผ์ด๊ฐ ๋ฝ์๋ด๋ ค๊ณ ํ๋ ์์ ์์น๊ฐ www.acmicpc.net ์ด ๋ฌธ์ ๋ index๋ง ์ฐ๋ฉด ๊ธ๋ฐฉ ํด๊ฒฐํ ์ ์๋ค. ์ฒ์์๋ ๊ทธ๋ฅ ํ์ ๊ฐ์ฅ ์ ์์(q[0])์ ๋น๊ตํด์ ํด๊ฒฐํ๋๋ก ์ฝ๋๋ฅผ ์งฐ๋๋ ์ต์๊ฐ์ด ์๋๋ผ ์ต๋๊ฐ์ ๊ฐ๊น์ด ๊ฐ์ ๊ณ์ฐํ๊ณ ์๋ค๋ ๊ฑธ ์๊ฒ ๋์๋ค. ๊ทธ๋์ ์ด๋ป๊ฒ ํด๊ฒฐํ๋ฉด ์ข์๊น, ๊ณ ๋ฏผํ๋ค๊ฐ popํ๊ณ ์ ํ๋ ์ซ์์ ์๊ณผ ๋ค์ ๊ธธ์ด๋ฅผ ๋น๊ตํด ์งง์ ์ชฝ์ผ๋ก ์ฐ์ฐ(๋๋ฒ์งธ or ์ธ๋ฒ์งธ)์ ํ๋ฉด ๊ธ๋ฐฉ ํด๊ฒฐ๋๋ค๋ ๊ฑธ ์์๋ค. index ํจ์๋ ์๊ฐ๋ณต์ก๋๊ฐ O(1)..
2021.04.02 -
๋ฐฑ์ค 1550๋ฒ ํ์ด์ฌ
1550๋ฒ์ ๋ธ๋ก ์ฆV๋ก solved.ac๋ฅผ ์ ์ฉํ์๋ ๊ฐ์ฅ ๋ฎ์ ๋ ๋ฒจ ๋ฌธ์ ์ค ํ๋๋ค. ๊ทธ๋ฐ๋ฐ ๋ธ๋ก ์ฆ ๋ฌธ์ ๊ฐ.. ์ข ์ข ์ ํ๋ฆด ๋๊ฐ ์๋ค๋ ๊ฑธ ์๊ณ ์ฝ๋ฉ์ด ์ ์๋๊ฑฐ๋ ๋ค๋ฅธ ํ ์ผ์ด ํ๊ธฐ ์ซ์ ๋ ์ข ์ข ํ ๋ ๊ฐ์ฉ ํ๊ฒ ๋๋ ๊ฒ ๊ฐ๋ค. 1550๋ฒ์ ์ฐ์ www.acmicpc.net/problem/1550 1550๋ฒ: 16์ง์ ์ฒซ์งธ ์ค์ 16์ง์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์ด ์์ ์ต๋ ๊ธธ์ด๋ 6๊ธ์์ด๋ค. 16์ง์ ์๋ 0~9์ A~F๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , A~F๋ 10~15๋ฅผ ๋ปํ๋ค. ๋, ์ด ์๋ ์์ด ์๋ ์ ์์ด๋ค. www.acmicpc.net ์ง์ ๋ฌธ์ ๋ค. 10์ง์ 8์ง์ 16์ง์.. ๋ฑ๋ฑ์ ๋ฌธ์ ๋ฅผ ๋ณผ ๋๋ง๋ค ํญ์ ํท๊ฐ๋ฆฌ๋ ๊ฒ ๊ฐ๋ค. ๋์ค์ ํ๋ฃจ๋ฅผ ์ก๊ณ ์ง์์ ๋ํ ๊ฐ๋ ์ ๋ค์ ์ ๋ฆฌํ ํ์๊ฐ ์๋ค. ํ์ด์ฌ ๋ ํ์ด..
2021.03.27