호지

DP와 비트마스킹을 활용한 풀이이다. 처음에 _max값을 INT_MAX를 줬다가 틀렸습니다가 떠서 헤맸다 INT_MAX값이면 DFS의 return 값이 INT_MAX가 나올 수 있으므로 min값을 구할 때 버퍼오버플로우가 발생하므로 잘못된 결과가 도출된다. _max값을 적절히 설정하는 것도 중요하다. 외판원 순회에선 최소비용이 발생하는 경로를 찾는 것인데 어차피 모든 도시를 방문하기에 시작점이 어디든 상관이 없다. 따라서 0번을 시작점으로 하여 DFS를 돌리고 비트마스크가 모두 1이 됬을 때 방문한 도시에서 0번 도시로 향하는 경로가 있어야 순회가 가능한 경우이다. DFS의 x는 현재 방문한 도시 번호를, visited는 방문했던 도시에 대한 정보를 비트 마스크로 담고있다. dp배열은 _max값으로 초기..

dp와 비트마스크를 활용한 문제. 배열 dp[x][y][z]에서 x는 계단수의 길이, y는 0~9인 숫자, z는 비트마스크로 사용된 숫자를 체크한다. 길이가 1이면서 숫자 1~9가 사용되었을 때 dp를 채운다 (0으로 시작하는 수는 계단수가 아니므로 0은 제외) 길이가 2~n일때(len for문) 숫자 0~9에 대해(num for문) 비트마스크 0000000000~1111111111일 때(i for문) dp값을 채운다. i for문에서 해당 비트마스크를 순차탐색하여 dp를 채울 수 있는 이유는 길이가 1일때, dp[1][1][2], dp[1][2][4], dp[1][3][8]...이 1이고, 길이가 2일때, dp[2][0][3], dp[2][1][6], dp[2][2][1], dp[2][2][12].....