์๊ณ ๋ฆฌ์ฆ85 [Java] BOJ 7662 ์ด์ค ์ฐ์ ์์ ํ ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7662์ด์ค ์ฐ์ ์์ ํ(dual priority queue)๋ ์ ํ์ ์ธ ์ฐ์ ์์ ํ์ฒ๋ผ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ , ์ญ์ ํ ์ ์๋ ์๋ฃ ๊ตฌ์กฐ์ด๋ค.์ ํ์ ์ธ ํ์์ ์ฐจ์ด์ ์ ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ ๋ ์ฐ์ฐ(operation) ๋ช ๋ น์ ๋ฐ๋ผ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๋ฐ์ดํฐ ๋๋ ๊ฐ์ฅ ๋ฎ์ ๋ฐ์ดํฐ ์ค ํ๋๋ฅผ ์ญ์ ํ๋ ์ ์ด๋ค.์ด์ค ์ฐ์ ์์ ํ๋ฅผ ์ํด์ ๋ ๊ฐ์ง ์ฐ์ฐ์ด ์ฌ์ฉ๋๋๋ฐ, ํ๋๋ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ ํ๋ ์ฐ์ฐ์ด๊ณ ๋ค๋ฅธ ํ๋๋ ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ๋ ์ฐ์ฐ์ด๋ค.๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ๋ ์ฐ์ฐ์ ๋ ๋ ๊ฐ์ง๋ก ๊ตฌ๋ถ๋๋๋ฐ ํ๋๋ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๊ฒ์ ์ญ์ ํ๊ธฐ ์ํ ๊ฒ์ด๊ณ ๋ค๋ฅธ ํ๋๋ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋ฎ์ ๊ฒ์ ์ญ์ ํ๊ธฐ ์ํ ๊ฒ์ด๋ค.์ ์๋ง ์ ์ฅํ๋ ์ด์ค ์ฐ์ ์์ ํ Q๊ฐ ์๋ค๊ณ .. 2024. 9. 7. [Java] BOJ 16928 ๋ฑ๊ณผ ์ฌ๋ค๋ฆฌ ๊ฒ์ ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/16928๋ฑ๊ณผ ์ฌ๋ค๋ฆฌ ๊ฒ์์ ์ฆ๊ฒจ ํ๋ ํ๋ธ๋ฌ๋ฒ๋ ์ด๋ ๋ ๊ถ๊ธํ ์ ์ด ์๊ฒผ๋ค.์ฃผ์ฌ์๋ฅผ ์กฐ์ํด ๋ด๊ฐ ์ํ๋ ์๊ฐ ๋์ค๊ฒ ๋ง๋ค ์ ์๋ค๋ฉด, ์ต์ ๋ช ๋ฒ๋ง์ ๋์ฐฉ์ ์ ๋์ฐฉํ ์ ์์๊น?๊ฒ์์ ์ ์ก๋ฉด์ฒด ์ฃผ์ฌ์๋ฅผ ์ฌ์ฉํ๋ฉฐ, ์ฃผ์ฌ์์ ๊ฐ ๋ฉด์๋ 1๋ถํฐ 6๊น์ง ์๊ฐ ํ๋์ฉ ์ ํ์๋ค. ๊ฒ์์ ํฌ๊ธฐ๊ฐ 10×10์ด๊ณ , ์ด 100๊ฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ ๋ณด๋ํ์์ ์งํ๋๋ค. ๋ณด๋ํ์๋ 1๋ถํฐ 100๊น์ง ์๊ฐ ํ๋์ฉ ์์๋๋ก ์ ํ์ ธ ์๋ค. ํ๋ ์ด์ด๋ ์ฃผ์ฌ์๋ฅผ ๊ตด๋ ค ๋์จ ์๋งํผ ์ด๋ํด์ผ ํ๋ค. ์๋ฅผ ๋ค์ด, ํ๋ ์ด์ด๊ฐ i๋ฒ ์นธ์ ์๊ณ , ์ฃผ์ฌ์๋ฅผ ๊ตด๋ ค ๋์จ ์๊ฐ 4๋ผ๋ฉด, i+4๋ฒ ์นธ์ผ๋ก ์ด๋ํด์ผ ํ๋ค. ๋ง์ฝ ์ฃผ์ฌ์๋ฅผ ๊ตด๋ฆฐ ๊ฒฐ๊ณผ๊ฐ 100๋ฒ ์นธ์ ๋์ด๊ฐ๋ค๋ฉด .. 2024. 9. 7. [Java] BOJ 7576 ํ ๋งํ ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7576์ฒ ์์ ํ ๋งํ ๋์ฅ์์๋ ํ ๋งํ ๋ฅผ ๋ณด๊ดํ๋ ํฐ ์ฐฝ๊ณ ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ํ ๋งํ ๋ ์๋์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๊ฒฉ์ ๋ชจ์ ์์์ ์นธ์ ํ๋์ฉ ๋ฃ์ด์ ์ฐฝ๊ณ ์ ๋ณด๊ดํ๋ค.์ฐฝ๊ณ ์ ๋ณด๊ด๋๋ ํ ๋งํ ๋ค ์ค์๋ ์ ์ต์ ๊ฒ๋ ์์ง๋ง, ์์ง ์ต์ง ์์ ํ ๋งํ ๋ค๋ ์์ ์ ์๋ค.๋ณด๊ด ํ ํ๋ฃจ๊ฐ ์ง๋๋ฉด, ์ต์ ํ ๋งํ ๋ค์ ์ธ์ ํ ๊ณณ์ ์๋ ์ต์ง ์์ ํ ๋งํ ๋ค์ ์ต์ ํ ๋งํ ์ ์ํฅ์ ๋ฐ์ ์ต๊ฒ ๋๋ค.ํ๋์ ํ ๋งํ ์ ์ธ์ ํ ๊ณณ์ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ, ์, ๋ค ๋ค ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ฅผ ์๋ฏธํ๋ค. ๋๊ฐ์ ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ค์๊ฒ๋ ์ํฅ์ ์ฃผ์ง ๋ชปํ๋ฉฐ, ํ ๋งํ ๊ฐ ํผ์ ์ ์ ๋ก ์ต๋ ๊ฒฝ์ฐ๋ ์๋ค๊ณ ๊ฐ์ ํ๋ค.์ฒ ์๋ ์ฐฝ๊ณ ์ ๋ณด๊ด๋ ํ ๋งํ ๋ค์ด ๋ฉฐ์น ์ด ์ง๋๋ฉด ๋ค ์ต๊ฒ ๋๋์ง, ๊ทธ ์ต์.. 2024. 9. 2. [Java] BOJ 7569 ํ ๋งํ ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/7569์ฒ ์์ ํ ๋งํ ๋์ฅ์์๋ ํ ๋งํ ๋ฅผ ๋ณด๊ดํ๋ ํฐ ์ฐฝ๊ณ ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ํ ๋งํ ๋ ์๋์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๊ฒฉ์๋ชจ์ ์์์ ์นธ์ ํ๋์ฉ ๋ฃ์ ๋ค์, ์์๋ค์ ์์ง์ผ๋ก ์์ ์ฌ๋ ค์ ์ฐฝ๊ณ ์ ๋ณด๊ดํ๋ค.์ฐฝ๊ณ ์ ๋ณด๊ด๋๋ ํ ๋งํ ๋ค ์ค์๋ ์ ์ต์ ๊ฒ๋ ์์ง๋ง, ์์ง ์ต์ง ์์ ํ ๋งํ ๋ค๋ ์์ ์ ์๋ค.๋ณด๊ด ํ ํ๋ฃจ๊ฐ ์ง๋๋ฉด, ์ต์ ํ ๋งํ ๋ค์ ์ธ์ ํ ๊ณณ์ ์๋ ์ต์ง ์์ ํ ๋งํ ๋ค์ ์ต์ ํ ๋งํ ์ ์ํฅ์ ๋ฐ์ ์ต๊ฒ ๋๋ค.ํ๋์ ํ ๋งํ ์ ์ธ์ ํ ๊ณณ์ ์, ์๋, ์ผ์ชฝ, ์ค๋ฅธ์ชฝ, ์, ๋ค ์ฌ์ฏ ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ฅผ ์๋ฏธํ๋ค. ๋๊ฐ์ ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ค์๊ฒ๋ ์ํฅ์ ์ฃผ์ง ๋ชปํ๋ฉฐ, ํ ๋งํ ๊ฐ ํผ์ ์ ์ ๋ก ์ต๋ ๊ฒฝ์ฐ๋ ์๋ค๊ณ ๊ฐ์ ํ๋ค.์ฒ ์๋ ์ฐฝ๊ณ ์ ๋ณด๊ด๋ ํ .. 2024. 9. 1. [Java] BOJ 5430 AC ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/5430์ ์์ด๋ ์ฃผ๋ง์ ํ ์ผ์ด ์์ด์ ์๋ก์ด ์ธ์ด AC๋ฅผ ๋ง๋ค์๋ค. AC๋ ์ ์ ๋ฐฐ์ด์ ์ฐ์ฐ์ ํ๊ธฐ ์ํด ๋ง๋ ์ธ์ด์ด๋ค.์ด ์ธ์ด์๋ ๋ ๊ฐ์ง ํจ์ R(๋ค์ง๊ธฐ)๊ณผ D(๋ฒ๋ฆฌ๊ธฐ)๊ฐ ์๋ค.ํจ์๋ ์กฐํฉํด์ ํ ๋ฒ์ ์ฌ์ฉํ ์ ์๋ค.์๋ฅผ ๋ค์ด, "AB"๋ A๋ฅผ ์ํํ ๋ค์์ ๋ฐ๋ก ์ด์ด์ B๋ฅผ ์ํํ๋ ํจ์์ด๋ค. ์๋ฅผ ๋ค์ด, "RDD"๋ ๋ฐฐ์ด์ ๋ค์ง์ ๋ค์ ์ฒ์ ๋ ์๋ฅผ ๋ฒ๋ฆฌ๋ ํจ์์ด๋ค.๋ฐฐ์ด์ ์ด๊ธฐ๊ฐ๊ณผ ์ํํ ํจ์๊ฐ ์ฃผ์ด์ก์ ๋, ์ต์ข ๊ฒฐ๊ณผ๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.ํจ์ R์ ๋ฐฐ์ด์ ์๋ ์์ ์์๋ฅผ ๋ค์ง๋ ํจ์์ด๊ณ , D๋ ์ฒซ ๋ฒ์งธ ์๋ฅผ ๋ฒ๋ฆฌ๋ ํจ์์ด๋ค. ๋ฐฐ์ด์ด ๋น์ด์๋๋ฐ D๋ฅผ ์ฌ์ฉํ ๊ฒฝ์ฐ์๋ ์๋ฌ๊ฐ ๋ฐ์ํ๋ค.์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ .. 2024. 8. 31. [Java] BOJ 14940 ์ฌ์ด ์ต๋จ๊ฑฐ๋ฆฌ ๋ฌธ์ ๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/14940์ง๋๊ฐ ์ฃผ์ด์ง๋ฉด ๋ชจ๋ ์ง์ ์ ๋ํด์ ๋ชฉํ์ง์ ๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ์ฌ๋ผ.๋ฌธ์ ๋ฅผ ์ฝ๊ฒ ๋ง๋ค๊ธฐ ์ํด ์ค์ง ๊ฐ๋ก์ ์ธ๋ก๋ก๋ง ์์ง์ผ ์ ์๋ค๊ณ ํ์.์ง๋์ ํฌ๊ธฐ n๊ณผ m์ด ์ฃผ์ด์ง๋ค. n์ ์ธ๋ก์ ํฌ๊ธฐ, m์ ๊ฐ๋ก์ ํฌ๊ธฐ๋ค.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)๋ค์ n๊ฐ์ ์ค์ m๊ฐ์ ์ซ์๊ฐ ์ฃผ์ด์ง๋ค. 0์ ๊ฐ ์ ์๋ ๋ ์ด๊ณ 1์ ๊ฐ ์ ์๋ ๋ , 2๋ ๋ชฉํ์ง์ ์ด๋ค. ์ ๋ ฅ์์ 2๋ ๋จ ํ๊ฐ์ด๋ค.๊ฐ ์ง์ ์์ ๋ชฉํ์ง์ ๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅํ๋ค. ์๋ ๊ฐ ์ ์๋ ๋ ์ธ ์์น๋ 0์ ์ถ๋ ฅํ๊ณ , ์๋ ๊ฐ ์ ์๋ ๋ ์ธ ๋ถ๋ถ ์ค์์ ๋๋ฌํ ์ ์๋ ์์น๋ -1์ ์ถ๋ ฅํ๋ค.์์ด๋์ด๊ธธ ์ ๋ณด๋ฅผ 2์ฐจ์ ๋ฐฐ์ด์ ์ ์ฅํ๋๋ฐ ์ด๋ ๊ฐ์ด 2๊ฐ ๋ค์ด์จ๋ค.. 2024. 8. 28. ์ด์ 1 2 3 4 ยทยทยท 15 ๋ค์