DP 의 기본적인 구조는 이 4가지라고 할 수 있다.

기저사례, 메모이제이션, 로직, 초기화

---

2098 외판원 순회 (G1)

문제 링크
dp[i][j]는 현재 도시가 i이고 j번째 비트가 1로 설정된 상태에서의 최소 비용을 나타낸다.

방문 순서가 상관이 없다. 포함여부를 다차원배열로 만들지 않고
tsp함수의 int형 매개변수인 visited에 비트마스킹으로 체크해준다.

만약 모든 지점을 방문했다면, dist[here][0]이 있다면 (출발지점으로 돌아오는 길이 있다면) dist[here][0]을 리턴하고 그렇지 않다면 (출발지점으로 돌아오는 길이 없다면) INF를 반환한다. 왜 INF를 반환하냐? 배제하기 위해서다. 최솟값을 구하는 문제이므로~

#include <bits/stdc++.h> 
using namespace std; 

#define MAX_N 16
const int INF = 987654321;
int n, dp[MAX_N][1 << MAX_N], dist[MAX_N][MAX_N];

int tsp(int here, int visited){
    if(visited == (1 << n) - 1){
        return dist[here][0] ? dist[here][0] : INF;
	}
    
    // 메모이제이션
    int &ret = dp[here][visited];
    if(ret != -1) return ret;
    ret = INF; // 최솟값은 최댓값부터 시작한다
    
    for(int i = 0; i < n; i++){
        if(visited & (1 << i)) continue; //방문했다면
        if(dist[here][i] == 0) continue; //경로가 없다면
        ret = min(ret, tsp(i, visited | (1 << i)) + dist[here][i]);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> dist[i][j];
        }
    }
    
    memset(dp, -1, sizeof(dp)); // 초기화는 답이 될 수 없는 범위로 
    cout << tsp(0, 1) << '\n';
    return 0;
}

---

if(visited == (1 << n) - 1)

if(visited == (1 << n) - 1) 구문은 현재까지 방문한 도시들의 상태를 나타내는 visited 변수가 모든 도시를 방문한 상태인지를 체크하는 조건이다.

여기서 (1 << n)은 2의 n승을 나타낸다. 이는 n비트 중에서 한 비트만 1이고 나머지는 0인 값을 갖는다. 즉, n 비트 중에서 하나만 1로 설정된 비트열이 된다.

(1 << n) - 1은 n비트 모두를 1로 설정한 값이다. 예를 들어, 만약 n이 4라면 (1 << 4) - 1은 1111이 된다.

따라서 if(visited == (1 << n) - 1) 구문은 모든 도시를 방문했는지를 확인하는 조건이 되는데, 이 조건이 참이라면 모든 도시를 방문했다는 의미이다.

왜 dp[MAX_N][MAX_N] 가 아니고 dp[MAX_N][1 << MAX_N] 인지?

예를 들어, MAX_N이 4이고 4개의 도시가 있다고 가정하자

경우 1 dp[MAX_N][MAX_N]

dp 배열은 크기가 4x4인 2차원 배열입니다. 즉, dp[4][4] 형태이다.
여기서 dp[i][j]는 현재 i번째 도시에 있고, j번째 도시를 방문했을 때의 최소 비용을 저장한다.
예를 들어, dp[2][3]은 두 번째 도시에 있고, 3번째 도시를 방문했을 때의 최소 비용을 나타낸다.
이 경우, 각각의 열은 j번째 도시를 방문했는지 여부를 나타내고, 각각의 행은 현재 위치하는 도시를 나타낸다. 하지만 이 방식은 모든 경우의 수에 대한 상태를 저장하므로 메모리 사용이 증가할 수 있다.

경우 2 dp[MAX_N][1 << MAX_N]

dp 배열은 크기가 4x16인 2차원 배열입니다. 즉, dp[4][16] 형태이다.
여기서 dp[i][j]는 현재 i번째 도시에 있고, j라는 비트마스크로 도시 방문 상태를 나타낸다.
예를 들어, dp[2][9]는 두 번째 도시에 있고, 도시 1과 도시 3을 방문했을 때의 최소 비용을 나타낸다.
이 경우, 각각의 열은 비트마스크로 도시 방문 상태를 나타내므로, 상태의 수가 줄어들어 메모리를 더 효율적으로 사용할 수 있다.

결론적으로, dp[MAX_N][1 << MAX_N]을 사용하는 것은 메모리 사용을 효율적으로 하면서도 문제를 해결할 수 있는 방법이다.

---

17070 파이프 옮기기 1 (G5)

문제 링크

#include <bits/stdc++.h>
using namespace std;   
void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);   
}  
int n, a[24][24], dp[24][24][3];
bool check(int y, int x, int d){
    if(d == 0 || d == 2){
        if(!a[y][x]) return true; 
    }else if(d == 1){
        if(a[y][x] == 0 && a[y - 1][x] == 0 && a[y][x - 1] == 0) return true; 
    }
    return false; 
}
int main(){
    fastIO();
    cin >> n; 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> a[i][j];
        }
    }
    dp[1][2][0] = 1; 
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(check(i, j + 1, 0))dp[i][j + 1][0] += dp[i][j][0];
            if(check(i + 1, j + 1, 1))dp[i + 1][j + 1][1] += dp[i][j][0]; 

            if(check(i + 1, j, 2))dp[i + 1][j][2] += dp[i][j][2];
            if(check(i + 1, j + 1, 1))dp[i + 1][j + 1][1] += dp[i][j][2]; 
            
            if(check(i, j + 1, 0))dp[i][j + 1][0] += dp[i][j][1];
            if(check(i + 1, j, 2))dp[i + 1][j][2] += dp[i][j][1];
            if(check(i + 1, j + 1, 1))dp[i + 1][j + 1][1] += dp[i][j][1];  
        }
    }   
    int ret = dp[n][n][0]; 
    ret += dp[n][n][1]; ret += dp[n][n][2];  
    cout << ret << "\n"; 
    return 0;
} 

---