https://www.acmicpc.net/problem/1562   이 문제는 어떠한 수 N 이 주어졌을 때 각자리수를 이동할때마다 1 씩 차이나는수를 계단수로 정의하고 N의 자릿수를 가지며 0~9 까지 모든 수가 등장하는 계단 수의갯수를 구하는 문제이다. 처음 문제를 마주했을때 문제를 이해하지 못했다. DP를 활용해야하며 비트마스킹을활용해야한다는 팁을 보고서도 문제를 풀이할 방법을 찾지 못했다. dp 3차원 배열을 활용, 비트마스킹을 활용한 방법을 설명 하겠다.dp[][][] 3차원배열의 각 차수에는 첫째 몇번째 자리수 인지 i 둘째 마지막 숫자가 무엇인지 j셋째 그 숫자의 check 상태는 어떠한지(비트마스킹)을 활용한다. dp 는 초기 설정, 점화식 이 제일 중요하다고 본다. 초기설정은 dp 의 ..

https://www.acmicpc.net/problem/2098   이 문제는 외판원 순회 문제를 해결하기 위해 동적 계획법과 비트마스크를 활용하였다.먼저 도시 수 N과 도시 간 이동 비용을 입력받고, 이동 불가능한 경로는 INF로 설정한다.dist 배열에는 각 도시 간의 이동 비용이 저장되고, dp 배열은 특정 방문 상태와 현재 위치에서의 최소 비용을 저장하는 데 사용된다.시작점인 0번 도시는 이미 방문한 상태로 초기화되며, 나머지는 초기값으로 설정된다.tsp 메서드는 모든 도시를 방문하는 경로를 비트마스크로 나타내어 각 상태를 갱신한다. 현재 방문한 도시 집합과 위치를 기준으로,다음에 방문할 도시를 확인하며 비용을 갱신한다.만약 이미 방문한 도시거나,이동이 불가능한 도시라면 건너뛴다.모든 상태를 처..