โญ Problem_Solving44 [๋ฐฑ์ค] 1368 ๋ฌผ๋๊ธฐ (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/1368 1368๋ฒ: ๋ฌผ๋๊ธฐ ์ฒซ ์ค์๋ ๋ ผ์ ์ N(1 ≤ N ≤ 300)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ i๋ฒ์งธ ๋ ผ์ ์ฐ๋ฌผ์ ํ ๋ ๋๋ ๋น์ฉ Wi(1 ≤ Wi ≤ 100,000)๊ฐ ์์๋๋ก ๋ค์ด์จ๋ค. ๋ค์ N๊ฐ์ ์ค์ ๋ํด์๋ ๊ฐ ์ค์ N๊ฐ์ ์๊ฐ ๋ค์ด www.acmicpc.net ๋ ผ ์ฐ๊ฒฐ ๋ถ๋ถ์ด๋ ๋ฌธ์ ์ ๋ณด๋ฅผ ๋ณด๋ฉด ๋ญ๊ฐ ๊ทธ๋ํ๋ ์ต์์ ์ฅํธ๋ฆฌ๋ฅผ ์ฌ์ฉํด์ผํ ๊ฒ ๊ฐ์๋ฐ '์ฐ๋ฌผ ํ๊ธฐ'๋ฅผ ์ด๋ป๊ฒ ์ฒ๋ฆฌํ ์ง๊ฐ ๊ด๊ฑด์ด๋ค. ๊ฒฐ๋ก ์ ์ผ๋ก ์ฐ๋ฌผ์ ๋ํ๋ด๋ ๊ฐ์์ ๋ ธ๋ N+1๋ฒ ๋ ธ๋๋ฅผ ๋ง๋ค๊ณ ํด๋น ๋ ธ๋์ ๊ฐ์ ๋น์ฉ์ ์ฐ๋ฌผ ํ๋ ๋น์ฉ์ผ๋ก ์ค์ ํด์ฃผ๋ฉด ๋๋ค. ๋๋จธ์ง๋ ์ผ๋ฐ์ ์ธ ์ต์์ ์ฅํธ๋ฆฌ ๋ฌธ์ ๋ ๋น์ทํ๋ค. ๊ฐ์์ ๋ ธ๋๋ฅผ ๋ง๋ค์ด์ค์ ์ ๋ ฅ๊ฐ์ ์ฒ๋ฆฌํ๋ ์ ๊ทผ์ด๋ ๋ฐ์์ด ์ค์ํ.. 2022. 10. 16. [๋ฐฑ์ค] 2252 ์ค ์ธ์ฐ๊ธฐ (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/2252 2252๋ฒ: ์ค ์ธ์ฐ๊ธฐ ์ฒซ์งธ ์ค์ N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. M์ ํค๋ฅผ ๋น๊ตํ ํ์์ด๋ค. ๋ค์ M๊ฐ์ ์ค์๋ ํค๋ฅผ ๋น๊ตํ ๋ ํ์์ ๋ฒํธ A, B๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ ํ์ A๊ฐ ํ์ B์ ์์ ์์ผ ํ๋ค๋ ์ www.acmicpc.net 1. ๊ธฐ๋ณธ์ ์ธ ์์ ์ ๋ ฌ ๋ฌธ์ ์ด๋ค. 2. ์์์ ๋ ฌ์ ๋ํ ์์ธํ ์ค๋ช ์ (๋งํฌ) from collections import deque import sys, os, io, atexit input = lambda: sys.stdin.readline().rstrip('\r\n') stdout = io.BytesIO() sys.stdout.write = lamb.. 2022. 10. 15. [๋ฐฑ์ค] 17471 ๊ฒ๋ฆฌ๋งจ๋๋ง (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/17471 17471๋ฒ: ๊ฒ๋ฆฌ๋งจ๋๋ง ์ ๊ฑฐ๊ตฌ๋ฅผ [1, 4], [2, 3, 5, 6]์ผ๋ก ๋๋๋ฉด ๊ฐ ์ ๊ฑฐ๊ตฌ์ ์ธ๊ตฌ๋ 9, 8์ด ๋๋ค. ์ธ๊ตฌ ์ฐจ์ด๋ 1์ด๊ณ , ์ด ๊ฐ๋ณด๋ค ๋ ์์ ๊ฐ์ผ๋ก ์ ๊ฑฐ๊ตฌ๋ฅผ ๋๋ ์๋ ์๋ค. www.acmicpc.net 1. ๋ถ๋ถ์งํฉ / ์กฐํฉ์ ํตํด์ ๋ ์ ๊ฑฐ๊ตฌ๋ฅผ ๊ตฌํ ๋ค์, ํด๋น ์ ๊ฑฐ๊ตฌ ๋ด์ ์ธ๊ตฌ์์ ๊ตฌ์ญ์๋ฅผ ๊ณ์ฐํด์ ๋ชจ๋ ๊ตฌ์ญ์ด ํฌํจ๋์์ ๊ฒฝ์ฐ์๋ง ์ ๋ต์ ๊ฐฑ์ ํด์ฃผ๋ฉด ๋๋ค. 2. ์กฐํฉ์ ๊ตฌํ ๋ ์ด์ฐจํผ ์กฐํฉ์ ํฌํจ๋์ง ๋ชปํ ๊ตฌ์ญ๋ค์ด ๋ค๋ฅธ ์ ๊ฑฐ๊ตฌ์ ํฌํจ๋๊ธฐ ๋๋ฌธ์ N//2๊น์ง๋ง ์กฐํฉ์ ๊ตฌํด๋ ๋๋ค. 3. ๊ทธ๋ฌ๋ N๊น์ง ๋ชจ๋ ์กฐํฉ์ ๊ตฌํด๋ ๋ณ ๋ฌธ์ ์์ด ์๊ฐ ๋ด์ ํต๊ณผ ๋๋ค. from collections import deque fro.. 2022. 10. 14. [๋ฐฑ์ค] 16236 ์๊ธฐ์์ด (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/16236 16236๋ฒ: ์๊ธฐ ์์ด N×N ํฌ๊ธฐ์ ๊ณต๊ฐ์ ๋ฌผ๊ณ ๊ธฐ M๋ง๋ฆฌ์ ์๊ธฐ ์์ด 1๋ง๋ฆฌ๊ฐ ์๋ค. ๊ณต๊ฐ์ 1×1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ํ ์นธ์๋ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์ต๋ 1๋ง๋ฆฌ ์กด์ฌํ๋ค. ์๊ธฐ ์์ด์ ๋ฌผ๊ณ ๊ธฐ๋ ๋ชจ๋ ํฌ๊ธฐ๋ฅผ ๊ฐ www.acmicpc.net ๊ตฌํ ๋ฌธ์ ์ด๋ค. ๋๊ฐ์ ๊ฒฝ์ฐ๋ ์ฒ์์ ์ต๋ O(N^6)์ ์ฝ๋๋ก pypy(1076ms)๋ก ํต๊ณผ (python ์๊ฐ์ด๊ณผ)ํ๊ณ ์ดํ์ jh05013๋์ ํ์ด๋ฅผ ์ฐธ๊ณ ํ์ฌ ํจ์ฌ ๋น ๋ฅธ ํ์ด(python: 288ms)๋ก ๋ค์ ํ์๋๋ฐ ๋ ๊ฐ์ง ๋ชจ๋ ์๊ฐํด๋ณด๊ฒ ๋ค. ๊ฐ์ฅ ์ค์ํ ๊ฒ์ ์์ด๊ฐ ๋ค์ ๋จน์ด๋ฅผ ์ฐพ์๊ฐ๋ ๊ณผ์ ์ ๊ตฌํํ๋ ๊ฒ์ธ๋ฐ, ์ฌ๊ธฐ์ '๊ฐ์ฅ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ๊น์ฐ๋ฉฐ, ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ ๊ฒฝ์ฐ ์ผ์ชฝ ์๋จ์ ์๋ .. 2022. 10. 13. [๋ฐฑ์ค] 12100 2048 (Easy) (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/12100 12100๋ฒ: 2048 (Easy) ์ฒซ์งธ ์ค์ ๋ณด๋์ ํฌ๊ธฐ N (1 ≤ N ≤ 20)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๊ฒ์ํ์ ์ด๊ธฐ ์ํ๊ฐ ์ฃผ์ด์ง๋ค. 0์ ๋น ์นธ์ ๋ํ๋ด๋ฉฐ, ์ด์ธ์ ๊ฐ์ ๋ชจ๋ ๋ธ๋ก์ ๋ํ๋ธ๋ค. ๋ธ๋ก์ ์ฐ์ฌ ์๋ ์๋ 2 www.acmicpc.net 1. N์ด 20 ์ดํ์ด๊ณ ์ํ์ด 5๋ฒ์ผ๋ก ๊ณ ์ ๋์ด ์์ด์ ๋ฐฑํธ๋ํน์ ์ด์ฉํ ์์ ํ์์ผ๋ก ๋ฌธ์ ๋ฅผ ํ ์ ์๋ค. 2. ๋ธ๋ญ์ ๋ณํฉ / ์ด๋ 2๊ฐ์ง๋ฅผ ์ํ์ข์ฐ 4๋ฐฉํฅ์ผ๋ก ๊ตฌํํด์ผ๋๋๋ฐ ๋๋ ํ ๋ฐฉํฅ์ ๋ํด์๋ง ๊ตฌํํ๊ณ ๋๋จธ์ง๋ ๋ฐฐ์ด์ ํ์ ์์ผ์ ์ ์ฉํ๋ ๋ฒ์ ์ด์ฉํ๋ค. (์ฐธ๊ณ : https://bluuubery.tistory.com/48?category=584396) 3. .. 2022. 10. 11. [๋ฐฑ์ค] 18405 ๊ฒฝ์์ ์ ์ผ (Python/ํ์ด์ฌ) https://www.acmicpc.net/problem/18405 18405๋ฒ: ๊ฒฝ์์ ์ ์ผ ์ฒซ์งธ ์ค์ ์์ฐ์ N, K๊ฐ ๊ณต๋ฐฑ์ ๊ธฐ์ค์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑธ์ณ์ ์ํ๊ด์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ์ N๊ฐ์ ์์๋ก ๊ตฌ์ฑ๋๋ฉฐ, ํด๋น ์์น www.acmicpc.net 1. ํ ๋งํ ๋ ๋น์ทํ๊ฒ ์ฒ์์ ๋ฐ์ด๋ฌ์ค์ ์ขํ๋ฅผ ํ์ ์ ์ฅํด๋๊ณ bfs๋ฅผ ๋๋ฆฌ๋ฉด๋๋ค. 2. ๋จ ์ด ๋ฌธ์ ์์๋ ๋ฎ์ ๋ฒํธ์ ๋ฐ์ด๋ฌ์ค๋ถํฐ ์ ์ผ๋๋ค๋ ํน์ฑ์ด ์์ผ๋ฏ๋ก bfs ๋๋ฆฌ๊ธฐ ์ง์ ์ ํ๋ฅผ ํ๋ฒ ์ ๋ ฌํด์ค์ผ ํ๋ค. from collections import deque import sys, os, io, atexit input = lambda: sys.stdin.readl.. 2022. 10. 10. ์ด์ 1 2 3 4 5 6 7 8 ๋ค์