์ ์ฒด ๊ธ
[๋ฐฑ์ค | BOJ] Good Bye, BOJ 2021! ํ๊ธฐ ๋ฐ ํ์ด (ABCD)
๋ฐฑ์ค์์๋ ์ฐ๋ง์ ๊ตฟ๋ฐ์ด ๋ฐฑ์ค, ์ฐ์ด์ ํฌ๋ก ๋ฐฑ์ค(๊ตฟ๋ชจ๋ ๋ฐฑ์ค) ํ์ฌ๊ฐ ์๋ค. 2021 ๋ฐฑ์ค ๋ง๋ฌด๋ฆฌํ ๊ฒธ ๋ฌธ์ ํ์ด. ๋ํ์์๋ 2์๋ธ, ๋๋๊ณ CD ์ ์๋น๊น์ง ํ๋ค. A. 2021์ ๋ฌด์์ด ํน๋ณํ ๊น? $N$ ๋ฒ์๊ฐ $10,000$์ด๋ค. ์์๋ฅผ ์ญ ๋์ด๋๊ณ , ๋๊ฐ๋ฅผ ๋ฏธ๋ฆฌ ๊ณฑํด๋๊ณ ์ด๋ถํ์ํด์ ํ์๋ค. ์ฌ์ค ์ด๋ถํ์์ ํ์๊ฐ ์๋๋ฐ. ์์ ๊ฐ์๊ฐ 30๊ฐ๊ฐ ์ ๋๋ค. ๋ฐฐ์ด์ ํ ๋ฐํด ๋ ๊ฑธ. $N = 10,000$์ผ ๋ 103๊น์ง ๋ฃ์ด๋ฌ์ผ ํ๋๋ฐ, ๋ฃ์ง ์์์ WA, ํ ์คํธํ๋ต์๊ณ ๋ฃ์ ์ฝ๋๋ฅผ ์ ์์ ์ WA. ์์ํ ์ค์๋ฅผ ๋ง์ด ํ๋ค. ์ ์ถ ์ ์๋ ๊ผญ ์ฒดํฌํ์. B. ์์ ์ผ์ดํฌ ๋ํ ์ค์๋ OEIS์ ํ์ ๋ฐ์์ ํ์๋ค. ์์ผ๋ก ์ค์ค ์ฐ๋ค๊ฐ ๋ญ๊ฐ ๊ท์น์ด ์๋ ๊ฒ ๊ฐ์์ ๋๊ฒผ๋ค. ์ฆ๋ช ์ ์๋์ ๊ฐ๋ค. $N ..
42์์ธ (42SEOUL) ์จ๋ผ์ธํ ์คํธ ํ๊ธฐ
1ํ๋ ์ ๋ง์น๊ณ ๊ณต๊ตฐ ์ ๋, 9์๋ง ์ ์ญ์ ํด๊ฐ ๋์์ ๋ณธ๊ฒฉ์ ์ผ๋ก ์ด๋ค ๊ณต๋ถ๋ฅผ ํ๋ฉด ์ข์๊น ๊ณ ๋ฏผ. ๋ค์ํ ์ฝ์ค๋ค์ ์ ํ๊ณ ๋ค์ด๋ณด๋๊ฒ ์ข๊ฒ ๋ค๊ณ ์๊ฐํ๋ค. ์ฌ๋ฟ ์์์ง๋ง ๋ด ๋๊ธธ์ ๋์๋ ๊ฑด ์ผ์ฑ SSAFY, ์ฐ์ํํ์ ๋ค ์ฐ์ํํ ํฌ์ฝ์ค, ์ด๋ ธ๋ฒ ์ด์ ์์นด๋ฐ๋ฏธ(์ ๋ถ) 42์์ธ. SSAFY๋ 4๋ ์ ์กธ์ ์ ๋ฐ ์กธ์ ์์ ์์๊ฒ ์ง์์๊ฒฉ์ด ์ฃผ์ด์ ธ ๋์๊ฒ๋ ํด๋น์ด ์ ๋๊ณ , ์ฐ์ํํ ํฌ์ฝ์ค๋ ๋ค์์ฃผ ์์์ผ(11/3)์ ์ ์๋ง๊ฐ์ด๋ผ ๊ณ ๋ฏผ์ค์ ์๋ค. ์์ธ42์์๋ ํ์ฌ ๋ชจ์ง์ค์ด ์๋๋ค. ๊ทธ๋๋ ์์ ์จ๋ผ์ธ ํ ์คํธ ๊ฒฐ๊ณผ๋ฅผ ํตํด ๊ต์ก๊ณผ์ ์ ์ ๊ณผํ ๊ธฐํ๋ฅผ ์ฃผ๊ธฐ์, ํ ์คํธ๋ฅผ ํ ๋ฒ ๋ดค๋ค. ํ ์คํธ๋ 4๋ถ, 2์๊ฐ์ด ์์๋๋ ๋ ๊ฐ์ง์ ๊ฒ์์ด ์ ๋ถ์ด๋ค. ํ ๋ฒ ๋ณด๊ณ ๋๋ฉด ๋ค์๋ ์ง์ํ ์ ์๋ค๋ ๊ฒ ๊ธด์ฅ๋๋ ๋ฐ ํ๋ชซํ๋ค. 4๋ถ์ด ๊ฑธ๋ ธ๋..
[๋ฐฑ์ค | BOJ] ๊ฐํฌ์ ํจ๊ป ํ๋ 2ํ ์ฝ๋ฉ ํ ์คํธ ํ๊ธฐ
์ ๋ฒ์ ์ฌ๋ฐ๊ฒ ํ์๋ ์๋ฆฌ์ฆ ๋ํ๊ฐ ์ด๋ ธ๋ค. 1ํ๋์ ๊ฐ์ด ๋ฌธ์ ๋ค์ด ์ฌ๋ฐ๋ค. ์ฒ์ ์๊ฐํ ํ์ด์๋ ๋ค๋ฅด๊ฒ ์๊ฐํ๋ ๋ฌธ์ ๋ค๋ ์์๋ค. 1์๋ถํฐ ๋ฐ์ง ์ฐธ์ฌํ์ง๋ ๋ชปํ์ง๋ง, 5๋ฌธ์ ๋ฅผ ํ์๋ค. ํ์ด๋ ์๋. ๊ฐํฌ์ ํจ๊ป ํ๋ 2ํ ์ฝ๋ฉ ํ ์คํธ www.acmicpc.net 1. ๊ฐํฌ์ ํ์ผ ํ์๊ธฐ ๋ฌธ์์ด ๊ด๋ จ ๋ฌธ์ ๋ฅผ ํ ๋๋ฉด ํ์ด์ฌ๋ฐ์ ๋ชป ํ๋ ๋๋ฅผ ์กฐ๊ธ์ ์ดํดํ ์ ์๊ฒ ๋๋ค.. ๋จ์ ์ ๋ ฌ ์ธ ๋ฒ์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ค. ์ฐ์ ์์์ ๋ฐ๋์์๋๋ก ์ ๋ ฌ์ ์งํํ๋ฉด, ์ฐ์ ์์๋ฅผ ๋ชจ๋ ๋ง์กฑํ๊ฒ๋ ์ ๋ ฌํ ์ ์๋ค. ํ์ผ๋ช ๊ณผ ํ์ฅ์๋ก ๋๋ ์ ๋ ฅ๋ฐ๊ณ , ์ง์ํ๋ ํ์ฅ์๋ค์ dict ๋ฅผ ํตํด ๊ด๋ฆฌํ ๋ค, key ๋ฅผ ๊ฐ๊ฐ ํ์ฅ์, ์ง์ ์ฌ๋ถ, ํ์ผ๋ช ์์๋๋ก ์ ๋ ฌ์ ์ธ ๋ฒ ํ๋ค. 2. ๊ฐํฌ์ ํค์๋ ์ด ๋ฌธ์ ๋ ๋ธ๋ฃจํธํฌ์ค๋ก ํด๊ฒฐํ๋ค...
[2021 Dev Carnival] ๋ฐ๋ธ์นด๋๋ฐ 2021 ์ฝ๋ฉํ ์คํธ ๊ธ์ ๋ฐฐ์ง ํ๊ธฐ (๋ฌธ์ ๋ณต๊ธฐ)
goorm.io์์ ์งํํ๋ 2021 Dev Carnival : ๋ฐ๋ธ ์นด๋๋ฐ์ ์ฐธ๊ฐํ๋ค ! 5์ 22์ผ์ ์งํ๋๋ ์ฝ๋ฉํ ์คํธ์๋๋ฐ, ์ผ๋ง ์ ์ ํ ์คํธ ๊ฒฐ๊ณผ๊ฐ ๋ฉ์ผ๋ก ๋ ์์๋ค. ์๊ณ ์์๋๋ฐ ๋ค์ ์๊ฐ๋์ ๊ธ์ ์ด๋ค. ํ ์คํธ๋ฅผ ํ๋ฉด์ ์์ฑํ ์ฝ๋๋ฅผ ๋ฐ๋ก ์ ์ฅํด๋์ง๋ ์์์ ์ ํํ ์ฝ๋๋ฅผ ๊ฐ์ง๊ณ ์์ง๋ ์๋ค. ๊ธฐ์ต๋๋ ๋๋ก ๋ฌธ์ ๋ฅผ ๋ณต๊ธฐํด๋ด์ผ๊ฒ ๋ค. 1๋ฒ ๋ฌธ์ ๋ ๋จ์๊ตฌํ ๋ฌธ์ ์๋ค. ์ฌ๋๋ง๋ค ๋จน์ ์ ์๋ ์์ ์์ด ์ ํด์ ธ ์๊ณ , ์์์ ์์๋๋ก ๋จน์ผ๋ฉฐ ์์ ๋๋ ์ฌ๋๋ค์ ์์๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ ์๋ค. ๋ฐฐ์ด ๋๋ ค๊ฐ๋ฉด์ ๋น ๋ฅด๊ฒ ํด๊ฒฐํ์๋ค. 2๋ฒ์ ๊ตฌํ์ด ์กฐ๊ธ ํ๋ค์ด๋ณด์ฌ์ 3, 4๋ฒ์ ๋จผ์ ๋ดค์๋ค. 3๋ฒ์ ๋ณด์๋ง์ DP๋ผ๋ ์๊ฐ์ด ๋ค์ด์ ๋๋ง์ณค๊ณ , 4๋ฒ ๋ฌธ์ ๋ฅผ ๋ถ์ก์๋ค. ๋จ๋ฐฉํฅ ๊ทธ๋ํ๊ฐ ์ฃผ์ด์ง๊ณ , ํ ๋ฒ ์ ์ ์ ๋ฐฉ๋ฌธํ ๋..
[๋ฐฑ์ค | BOJ] ๊ฐํฌ์ ํจ๊ป ํ๋ 1ํ ์ฝ๋ฉ ํ ์คํธ ํ๊ธฐ
์์ฆ ๋ฐฑ์ค์์ ๋ฌธ์ ๋ฅผ ์ข ํ๊ณ ์๋ค. ์ด๋ ค์ด ๊ณ ๊ธ์๊ณ ๋ฆฌ์ฆ๋ณด๋ค๋ ๋ํ๋ ์ฝ๋ฉํ ์คํธ์์ ์์ฃผ ๋ณด์ด๋ ์๊ณ ๋ฆฌ์ฆ ์์ฃผ๋ก ์ฐ์ตํ๋ ค๊ณ ํ๋ค. Codeforces์ Round๋, ๋ฐฑ์ค์ ๋ํ๋, Atcoder์ Contest ๋ชจ๋ ์ฐธ ์ข์ง๋ง, ์ ๋ถ์ด ๊ตฐ์ธ์ธ์ง๋ผ ์ฝ๊ฒ ์์ํ์ง ๋ชปํ๊ณ ์๋ค. ๊ฐํฌ์ ํจ๊ป ํ๋ 1ํ ์ฝ๋ฉ ํ ์คํธ www.acmicpc.net ์ค๋ ๊ด์ฐฎ์ ์๊ฐ๋์ ๋ํ๊ฐ ์ด๋ ค์ ์ฐธ๊ฐํ๊ฒ ๋๋ค. ๋ฌธ์ ๋ค์ ์ฌ๋ฐ์๊ณ , ๋ค์ํ ์๊ณ ๋ฆฌ์ฆ๋ค์ด ๋ฌธ์ ์ ์ ๋ น์์์ด์ ์ด๋ ๊ฒ์ ๋ ๊ฒ ํ์ด๋ณด๊ธฐ๋ ํ๋ค. ๊ณต์ง์ฌํญ์์ ๋ฏธ๋ฆฌ "๋น ๋ฅธ ์ ์ถ๋ ฅ"์ ์ฌ์ฉํ๋ผ๊ณ ์กฐ์ธํ์๋๋ฐ, ๊ฝค ํ ์คํธ์ผ์ด์ค๋ค์ด ๋ฌด๊ฑฐ์ด ๋ชจ์์ด๋ค. ํ์ด์ฌ์ผ๋ก ํ๊ฒน๊ฒ ๋์๊ฐ๋ค. ์ ๋ฒ ์๋ช ์ฌ๋ SMUPC์์๋ 2๋ฌธ์ ๋ง ํ๊ณ ๋ํ๋ฅผ ๋ง๋ฌด๋ฆฌํ์๋๋ฐ, ์ด๋ฒ ๋ํ์์๋ 8๋ฌธ์ ์ค์์ 6๋ฌธ..
[ํ์ด์ฌ | Python] ํธ๋ผ์ด (Trie) ์๋ฃ๊ตฌ์กฐ
๋ฌธ์์ด์ ํญ์ ์ด๋ ต๋ค. KMP๋ ๊ทธ๋ ๊ณ , digit์ผ๋ก ์ ๋ ฌํ๋ ๊ฒ๋ ๊ทธ๋ ๊ณ , ์๋ฉด ์์๋ก ๋จธ๋ฆฌ์ํ์ง๋ ๋ถ์ผ. ๊ทธ๋งํผ ์ด๋ ต๊ฒ ๋ง๋ค๋ฉด ํจ์ฌ ์ด๋ ต๊ฒ๋ ๋ง๋ค ์ ์๋ค๋ ์ด์ผ๊ธฐ๊ฒ ์ง. ์ค๋์ ํธ๋ผ์ด๋ฅผ ๊ณต๋ถํ๋ค. Radix tree / Prefix tree ๋ผ๊ณ ๋ ๋ถ๋ฆฌ๋๋ฐ, ํ ๋จ์ด์ ์ ๋์ฌ(์ ๋์ด)๋ฅผ ๋ชจ๋ ์ ์ฅํ๊ณ ์๋ค. (ํด๋น ๋จ์ด์ ๋๋ฌํ๊ธฐ๊น์ง์ ๋ฌธ์๋ค์ ์ ์ฅํ๋ค) donghoon ์ด๋ผ๋ ๋จ์ด๋ฅผ ๋ณด๋ฉด, dong ๋ ์ ๋์ฌ๊ฐ ๋ ์ ์๊ณ , do ๋ ์ ๋์ฌ๊ฐ ๋ ์ ์๋ค. ํธ๋ผ์ด์์๋ ์ด ๋จ์ด๋ค์ด ์๋ก ํฌํจ๊ด๊ณ์ ์๋ค๋ ๊ฒ์ ์๋ ค์ค๋ค. ํธ๋ผ์ด์ "app", "ant", "apple"์ด๋ผ๋ ๋จ์ด๋ค์ ์ ์ฅํ๋ค๊ณ ํ์. ํธ๋ผ์ด์๋ ์ง๊ธ๊น์ง์ ๋ชจ๋ ๋จ์ด์ ์์ทจ๋ฅผ ์ ์ฅํ๋ค๊ณ ํ๋ค. ๋จ์ด์ ๊ฐ ๊ธ์๋ง๋ค, ์กด์ฌํ์ง ์์ผ๋ฉด ์..
[ํ๋ก๊ทธ๋๋จธ์ค | Programmers] ์๊ฐ ์ฝ๋ ์ฑ๋ฆฐ์ง ์์ฆ2 5์ ๋ฌธ์ ํ์ด
ํ๋ก๊ทธ๋๋จธ์ค์์ ์๊ฐ ์ฝ๋ ์ฑ๋ฆฐ์ง๋ฅผ ์งํํ๋ค ! ์๊ฐ์ด ์ ์ ํ ์๊ฐ๋์ ์กํ์ ์ฌ์ ๋กญ๊ฒ ์ฐธ์ฌํ ์ ์์๋ค. 4์๋ฌ์ ํ ๋ฒ, ์ด๋ฒ ๋ฌ์ ํ ๋ฒ์ด ์์ฆ 2 ์ฑ๋ฆฐ์ง์๋๋ฐ, ๋๋ ์ด๋ฒ ์ฑ๋ฆฐ์ง๋ฅผ ๋ ๋ฒ์งธ ๋ํ๊ฐ ๋ผ์์ผ ์ ํ๋ค. ๋ ๋ฒ์งธ ๋ํ๊น์ง ์ด 8๋ฌธ์ ์ค์ 4๋ฌธ์ ๋ง ํ์ด๋ ์ด๋ฒคํธ์ ์๋ชจํ ์ ์๋ค๋๋ฐ, ์ด๋ฒ์ 3๋ฌธ์ ๋ฅผ ํ๋ฉด์ ์์ฝ๊ฒ ์๋ชจ๋ ํ์ง ๋ชปํ๋ค. ์ด๋ฒ ๋ฌ ์ฑ๋ฆฐ์ง์์๋ 6546๋ช ์ค 53์๋ฅผ ๋ฌ์ฑํ๋ค ! ๊ฐ์ธ์ ์ผ๋ก DP๊ฐ ๊ต์ฅํ ์ฝํ ํธ์ด๋ผ๊ณ ์๊ฐํ๋๋ฐ, ์ด๋ฒ ๋ฌธ์ ์ ์์๋ ๊ตฌํ / ๊ทธ๋ฆฌ๋ / ์๋ฃ๊ตฌ์กฐ / ๊ทธ๋ํ ์ชฝ์ผ๋ก ์ถ์ ๋ผ์ 3๋ฌธ์ ๋ฅผ ๋ง์๋ค. 1. ์ฝ์์ ๊ฐ์์ ๋ง์ ์ฝ์์ ๊ฐ์๊ฐ ์ง์๋ฉด ๋ํ๊ณ , ํ์๋ฉด ๋นผ์ผ ํ๋ค. ์ฝ์์ ๊ฐ์๊ฐ ํ์์ธ ๊ฒฝ์ฐ๋ ์ ๊ณฑ์์ธ ๊ฒฝ์ฐ์ด๊ณ , ์์ ๋ฒ์๊ฐ $1000$ ์ด๋๊น $3..
[๋ฐฑ์ค | BOJ] ์๋ช ์ฌ์๋ํ๊ต SMUPC ํ์ด๋ณด๊ธฐ
13์๋ถํฐ 17์๊น์ง 4์๊ฐ์ง๋ฆฌ ์คํ์ฝํ ์คํธ๊ฐ ์ด๋ ธ๋๋ฐ, ๋ค๋ฅธ ๋ฌธ์ ํธ๋๋ผ 30๋ถ๋์๋ฐ์ ๋ชป ํ์๋ค. ์ค๋ ๋ผ์ ์์นจ์ ๋ฌธ์ ํ์ด๋ณด๊ณ ํ์ด. ๋ฌด๋ํ๊ณ ์ฌ๋ฐ์๋ ๋ฌธ์ ์ ์ด์ง๋ง, ํ ์ชฝ์ ์น์ฐ์ณ์ง ์๊ณ ๋ฆฌ์ฆ ์ ์ด๋ผ๋ ์ ์ด ์์ฝ๋ค. ์ 1ํ ์๋ช ์ฌ์๋ํ๊ต ๊ต๋ด ์๊ณ ๋ฆฌ์ฆ ๊ฒฝ์ง๋ํ (SMUPC) Open www.acmicpc.net 21734: SMUPC์ ๋ฑ์ฅ ๊ฐ ์ํ๋ฒณ์ ์์คํค ์ฝ๋๋ฅผ ๊ตฌํ ๋ค์, ๊ฐ ์๋ฆฌ์๋ฅผ ๋ํ ๋งํผ ์ํ๋ฒณ์ ์ถ๋ ฅํ๋ฉด ๋๋ค. for i in input(): print(i * sum(list(map(int, list(str(ord(i))))))) 21735: ๋๋ฉ์ด ๊ตด๋ฆฌ๊ธฐ dp๋ก ํ๋ค๊ฐ ์๊ฐ๊น์ง ์ ์ฅ์ ์ด๋ป๊ฒ ํ์ง,, ๋ผ๋ ์๊ฐ์ ๋ํ๋ ์๋ ๋๊ธฐ๊ณ ์์นจ์ ๋ค์ ๋ณด๋ dfs๋ก ํ๊ณ ๋ด๋ ค๊ฐ๋ฉด ๋๋ ๋ฌธ์ ..