๐ ์๊ณ ๋ฆฌ์ฆ (130) ์ธ๋ค์ผํ ๋ฆฌ์คํธํ [C++/BOJ] 12865 : ํ๋ฒํ ๋ฐฐ๋ญ (DP) / ํ ์คํธ์ผ์ด์ค ํฌํจ https://www.acmicpc.net/problem/12865 ๋ฌธ์ ์ด ๋ฌธ์ ๋ ์์ฃผ ํ๋ฒํ ๋ฐฐ๋ญ์ ๊ดํ ๋ฌธ์ ์ด๋ค. ํ ๋ฌ ํ๋ฉด ๊ตญ๊ฐ์ ๋ถ๋ฆ์ ๋ฐ๊ฒ ๋๋ ์ค์๋ ์ฌํ์ ๊ฐ๋ ค๊ณ ํ๋ค. ์ธ์๊ณผ์ ๋จ์ ์ ์ฌํผํ๋ฉฐ ์ต๋ํ ์ฆ๊ธฐ๊ธฐ ์ํ ์ฌํ์ด๊ธฐ ๋๋ฌธ์, ๊ฐ์ง๊ณ ๋ค๋ ๋ฐฐ๋ญ ๋ํ ์ต๋ํ ๊ฐ์น ์๊ฒ ์ธ๋ ค๊ณ ํ๋ค. ์ค์๊ฐ ์ฌํ์ ํ์ํ๋ค๊ณ ์๊ฐํ๋ N๊ฐ์ ๋ฌผ๊ฑด์ด ์๋ค. ๊ฐ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ W์ ๊ฐ์น V๋ฅผ ๊ฐ์ง๋๋ฐ, ํด๋น ๋ฌผ๊ฑด์ ๋ฐฐ๋ญ์ ๋ฃ์ด์ ๊ฐ๋ฉด ์ค์๊ฐ V๋งํผ ์ฆ๊ธธ ์ ์๋ค. ์์ง ํ๊ตฐ์ ํด๋ณธ ์ ์ด ์๋ ์ค์๋ ์ต๋ K๋งํผ์ ๋ฌด๊ฒ๋ง์ ๋ฃ์ ์ ์๋ ๋ฐฐ๋ญ๋ง ๋ค๊ณ ๋ค๋ ์ ์๋ค. ์ค์๊ฐ ์ต๋ํ ์ฆ๊ฑฐ์ด ์ฌํ์ ํ๊ธฐ ์ํด ๋ฐฐ๋ญ์ ๋ฃ์ ์ ์๋ ๋ฌผ๊ฑด๋ค์ ๊ฐ์น์ ์ต๋๊ฐ์ ์๋ ค์ฃผ์. ์ ๋ ฅ ์ฒซ ์ค์ ๋ฌผํ์ ์ N(1 ≤ N ≤ 100.. [C++/BOJ] 1890 : ์ ํ (DP) https://www.acmicpc.net/problem/1890 ๋ฌธ์ N×N ๊ฒ์ํ์ ์๊ฐ ์ ํ์ ธ ์๋ค. ์ด ๊ฒ์์ ๋ชฉํ๋ ๊ฐ์ฅ ์ผ์ชฝ ์ ์นธ์์ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์๋ ์นธ์ผ๋ก ๊ท์น์ ๋ง๊ฒ ์ ํ๋ฅผ ํด์ ๊ฐ๋ ๊ฒ์ด๋ค. ๊ฐ ์นธ์ ์ ํ์๋ ์๋ ํ์ฌ ์นธ์์ ๊ฐ ์ ์๋ ๊ฑฐ๋ฆฌ๋ฅผ ์๋ฏธํ๋ค. ๋ฐ๋์ ์ค๋ฅธ์ชฝ์ด๋ ์๋์ชฝ์ผ๋ก๋ง ์ด๋ํด์ผ ํ๋ค. 0์ ๋ ์ด์ ์งํ์ ๋ง๋ ์ข ์ฐฉ์ ์ด๋ฉฐ, ํญ์ ํ์ฌ ์นธ์ ์ ํ์๋ ์๋งํผ ์ค๋ฅธ์ชฝ์ด๋ ์๋๋ก ๊ฐ์ผ ํ๋ค. ํ ๋ฒ ์ ํ๋ฅผ ํ ๋, ๋ฐฉํฅ์ ๋ฐ๊พธ๋ฉด ์ ๋๋ค. ์ฆ, ํ ์นธ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ์ ํ๋ฅผ ํ๊ฑฐ๋, ์๋๋ก ์ ํ๋ฅผ ํ๋ ๋ ๊ฒฝ์ฐ๋ง ์กด์ฌํ๋ค. ๊ฐ์ฅ ์ผ์ชฝ ์ ์นธ์์ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์๋ ์นธ์ผ๋ก ๊ท์น์ ๋ง๊ฒ ์ด๋ํ ์ ์๋ ๊ฒฝ๋ก์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ๊ฒ์ ํ์ ํฌ๊ธฐ N.. [C++/BOJ] 9251 : LCS (DP) https://www.acmicpc.net/problem/9251 ๋ฌธ์ LCS(Longest Common Subsequence, ์ต์ฅ ๊ณตํต ๋ถ๋ถ ์์ด)๋ฌธ์ ๋ ๋ ์์ด์ด ์ฃผ์ด์ก์ ๋, ๋ชจ๋์ ๋ถ๋ถ ์์ด์ด ๋๋ ์์ด ์ค ๊ฐ์ฅ ๊ธด ๊ฒ์ ์ฐพ๋ ๋ฌธ์ ์ด๋ค. ์๋ฅผ ๋ค์ด, ACAYKP์ CAPCAK์ LCS๋ ACAK๊ฐ ๋๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค๊ณผ ๋์งธ ์ค์ ๋ ๋ฌธ์์ด์ด ์ฃผ์ด์ง๋ค. ๋ฌธ์์ด์ ์ํ๋ฒณ ๋๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ์ต๋ 1000๊ธ์๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ๋ ๋ฌธ์์ด์ LCS์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ค. ๋ฐฑ์ค ๊ณจ๋5ํฐ์ด. ์ฒ์์ ์๊ฐ์ ํ์ด 0.1์ด๊ธธ๋ ์ํ์ผ๋ก๋ ๋ชปํ๊ฒ ๊ตฌ๋ ํ๋๋ฐ ์ญ์ ํ๋ฆผ ๊ทธ๋์ ์์ ํ DP๋ก ํด๊ฒฐํ์ต๋๋ค.. ์ ํ์์ ๋ ์ฌ๋ฆฌ๊ธฐ ํ๋ค์๋๋ฐ, ํ ๋ธ๋ก๊ฑฐ์ ์ ์ ๋ฆฌ๋ ๊ธ์ ์ฝ๊ณ ์ด์ฐจ์.. [C++/BOJ] 9465 : ์คํฐ์ปค (DP) https://www.acmicpc.net/problem/9465 ๋ฌธ์ ์๊ทผ์ด์ ์ฌ๋์ ์๋ฅ์ด๋ ๋ฌธ๋ฐฉ๊ตฌ์์ ์คํฐ์ปค 2n๊ฐ๋ฅผ ๊ตฌ๋งคํ๋ค. ์คํฐ์ปค๋ ๊ทธ๋ฆผ (a)์ ๊ฐ์ด 2ํ n์ด๋ก ๋ฐฐ์น๋์ด ์๋ค. ์๋ฅ์ด๋ ์คํฐ์ปค๋ฅผ ์ด์ฉํด ์ฑ ์์ ๊พธ๋ฏธ๋ ค๊ณ ํ๋ค. ์๋ฅ์ด๊ฐ ๊ตฌ๋งคํ ์คํฐ์ปค์ ํ์ง์ ๋งค์ฐ ์ข์ง ์๋ค. ์คํฐ์ปค ํ ์ฅ์ ๋ผ๋ฉด, ๊ทธ ์คํฐ์ปค์ ๋ณ์ ๊ณต์ ํ๋ ์คํฐ์ปค๋ ๋ชจ๋ ์ฐข์ด์ ธ์ ์ฌ์ฉํ ์ ์๊ฒ ๋๋ค. ์ฆ, ๋ ์คํฐ์ปค์ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ, ์, ์๋์ ์๋ ์คํฐ์ปค๋ ์ฌ์ฉํ ์ ์๊ฒ ๋๋ค. ๋ชจ๋ ์คํฐ์ปค๋ฅผ ๋ถ์ผ ์ ์๊ฒ๋ ์๋ฅ์ด๋ ๊ฐ ์คํฐ์ปค์ ์ ์๋ฅผ ๋งค๊ธฐ๊ณ , ์ ์์ ํฉ์ด ์ต๋๊ฐ ๋๊ฒ ์คํฐ์ปค๋ฅผ ๋ผ์ด๋ด๋ ค๊ณ ํ๋ค. ๋จผ์ , ๊ทธ๋ฆผ (b)์ ๊ฐ์ด ๊ฐ ์คํฐ์ปค์ ์ ์๋ฅผ ๋งค๊ฒผ๋ค. ์๋ฅ์ด๊ฐ ๋ ์ ์๋ ์คํฐ์ปค์ ์ ์์ ์ต๋๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์.. [C++/BOJ] 10971 : ์ธํ์ ์ํ 2 (์์ ํ์, dfs, Backtracking) https://www.acmicpc.net/problem/10971 ๋ฌธ์ ์ธํ์ ์ํ ๋ฌธ์ ๋ ์์ด๋ก Traveling Salesman problem (TSP) ๋ผ๊ณ ๋ถ๋ฆฌ๋ ๋ฌธ์ ๋ก computer science ๋ถ์ผ์์ ๊ฐ์ฅ ์ค์ํ๊ฒ ์ทจ๊ธ๋๋ ๋ฌธ์ ์ค ํ๋์ด๋ค. ์ฌ๋ฌ ๊ฐ์ง ๋ณ์ข ๋ฌธ์ ๊ฐ ์์ผ๋, ์ฌ๊ธฐ์๋ ๊ฐ์ฅ ์ผ๋ฐ์ ์ธ ํํ์ ๋ฌธ์ ๋ฅผ ์ดํด๋ณด์. 1๋ฒ๋ถํฐ N๋ฒ๊น์ง ๋ฒํธ๊ฐ ๋งค๊ฒจ์ ธ ์๋ ๋์๋ค์ด ์๊ณ , ๋์๋ค ์ฌ์ด์๋ ๊ธธ์ด ์๋ค. (๊ธธ์ด ์์ ์๋ ์๋ค) ์ด์ ํ ์ธํ์์ด ์ด๋ ํ ๋์์์ ์ถ๋ฐํด N๊ฐ์ ๋์๋ฅผ ๋ชจ๋ ๊ฑฐ์ณ ๋ค์ ์๋์ ๋์๋ก ๋์์ค๋ ์ํ ์ฌํ ๊ฒฝ๋ก๋ฅผ ๊ณํํ๋ ค๊ณ ํ๋ค. ๋จ, ํ ๋ฒ ๊ฐ๋ ๋์๋ก๋ ๋ค์ ๊ฐ ์ ์๋ค. (๋งจ ๋ง์ง๋ง์ ์ฌํ์ ์ถ๋ฐํ๋ ๋์๋ก ๋์์ค๋ ๊ฒ์ ์์ธ) ์ด๋ฐ ์ฌํ ๊ฒฝ๋ก๋ ์ฌ๋ฌ ๊ฐ.. [C++/BOJ] 9663 : N-Queen (์์ ํ์, Backtracking) https://www.acmicpc.net/problem/9663 ๋ฌธ์ N-Queen ๋ฌธ์ ๋ ํฌ๊ธฐ๊ฐ N × N์ธ ์ฒด์คํ ์์ ํธ N๊ฐ๋ฅผ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋๋ ๋ฌธ์ ์ด๋ค. N์ด ์ฃผ์ด์ก์ ๋, ํธ์ ๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. (1 ≤ N < 15) ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ํธ N๊ฐ๋ฅผ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ค. ๋ฌธ์ ํํธ์ ํธ์ Show must go on ๋ ธ๋๊ฐ ์๊ธธ๋ ์ ๋๊ฒ ๋ค์ผ๋ฉด์ ํ์์ ๋ฐฑ์ค ํฐ์ด ๊ณจ๋4, ์์ ํ์ + ๋ฐฑํธ๋ํน ๋ฌธ์ ์ด๋ค. ์ฒ์์ ๋ฐฑํธ๋ํน ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ๊ธด ํ์์ง๋ง ์ฌ๊ท ๊ณผ์ ์ด ์ ์ดํด๊ฐ ์๋์๋๋ฐ, ์ด๋ค ๋์์์ ์๋ ๊ทธ๋ฆผ์ ๋ณด๊ณ ๋ฐ๋ก ์ดํด๊ฐ ๋์๋ค. ์ฌ๊ท์ ํ๋ฆ๊ณผ ๋๊น์ ๋ฐ๋ก ๋ณผ ์ ์๋ ๊ทธ๋ฆผ์ด๋ค! main ide.. [C++/PGS] Lv.3 : N์ผ๋ก ํํ (DP) https://school.programmers.co.kr/learn/courses/30/lessons/42895 ๋ฌธ์ ์ค๋ช ์๋์ ๊ฐ์ด 5์ ์ฌ์น์ฐ์ฐ๋ง์ผ๋ก 12๋ฅผ ํํํ ์ ์์ต๋๋ค. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5๋ฅผ ์ฌ์ฉํ ํ์๋ ๊ฐ๊ฐ 6,5,4 ์ ๋๋ค. ๊ทธ๋ฆฌ๊ณ ์ด์ค ๊ฐ์ฅ ์์ ๊ฒฝ์ฐ๋ 4์ ๋๋ค. ์ด์ฒ๋ผ ์ซ์ N๊ณผ number๊ฐ ์ฃผ์ด์ง ๋, N๊ณผ ์ฌ์น์ฐ์ฐ๋ง ์ฌ์ฉํด์ ํํ ํ ์ ์๋ ๋ฐฉ๋ฒ ์ค N ์ฌ์ฉํ์์ ์ต์๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์ธ์. ์ ํ์ฌํญ N์ 1 ์ด์ 9 ์ดํ์ ๋๋ค. number๋ 1 ์ด์ 32,000 ์ดํ์ ๋๋ค. ์์์๋ ๊ดํธ์ ์ฌ์น์ฐ์ฐ๋ง ๊ฐ๋ฅํ๋ฉฐ ๋๋๊ธฐ ์ฐ์ฐ์์ ๋.. [C++/PGS] Lv.3 : ์์ (๊ทธ๋ํ/Floyd-Warshall) https://school.programmers.co.kr/learn/courses/30/lessons/49191# ๋ฌธ์ ์ค๋ช n๋ช ์ ๊ถํฌ์ ์๊ฐ ๊ถํฌ ๋ํ์ ์ฐธ์ฌํ๊ณ ๊ฐ๊ฐ 1๋ฒ๋ถํฐ n๋ฒ๊น์ง ๋ฒํธ๋ฅผ ๋ฐ์์ต๋๋ค. ๊ถํฌ ๊ฒฝ๊ธฐ๋ 1๋1 ๋ฐฉ์์ผ๋ก ์งํ์ด ๋๊ณ , ๋ง์ฝ A ์ ์๊ฐ B ์ ์๋ณด๋ค ์ค๋ ฅ์ด ์ข๋ค๋ฉด A ์ ์๋ B ์ ์๋ฅผ ํญ์ ์ด๊น๋๋ค. ์ฌํ์ ์ฃผ์ด์ง ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ๋ฅผ ๊ฐ์ง๊ณ ์ ์๋ค์ ์์๋ฅผ ๋งค๊ธฐ๋ ค ํฉ๋๋ค. ํ์ง๋ง ๋ช๋ช ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ๋ฅผ ๋ถ์คํ์ฌ ์ ํํ๊ฒ ์์๋ฅผ ๋งค๊ธธ ์ ์์ต๋๋ค. ์ ์์ ์ n, ๊ฒฝ๊ธฐ ๊ฒฐ๊ณผ๋ฅผ ๋ด์ 2์ฐจ์ ๋ฐฐ์ด results๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋ ์ ํํ๊ฒ ์์๋ฅผ ๋งค๊ธธ ์ ์๋ ์ ์์ ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ์ฌํญ ์ ์์ ์๋ 1๋ช ์ด์ 100๋ช ์ดํ์ ๋๋ค. ๊ฒฝ๊ธฐ .. ์ด์ 1 ยทยทยท 5 6 7 8 9 10 11 ยทยทยท 17 ๋ค์