목록2026/04/15 (1)
Miscellaneous
[BOJ/C++] 2098 - 외판원 순회
https://www.acmicpc.net/problem/2098 해당 문제는 이전에 풀었던 문제였음에도 불구하고, 최근 기업 코테에서 이와 비슷한 유형의 문제를 풀지 못했습니다. 아쉬운 마음에 복습하고자 해당 문제의 풀이를 작성합니다. 해당 문제는 백트래킹으로 구현할 시 O(16!)으로 시간초과가 발생합니다. 이 문제는 외판원 순회라는 well-known 유형입니다. 문제의 조건과 같이 n이 16이하일 때에는 비트마스킹 dp로 해결할 수 있습니다. dp 상태는 아래와 같이 정의합니다.dp[i][j] : 현재 위치가 i이고, 지금까지 j 도시를 방문했을 때의 최단거리n 2^16 = 65536이기 때문에 배열로 충분히 선언할 수 있는 크기입니다. 풀이 코드는 전형적인 비트마스킹 탑다운 dp 코드입..
Problem Solving/백준
2026. 4. 15. 21:27