[λ°±μ€/C++] 2098λ² μΈνμ μν
π€λ¬Έμ μ΄ν΄
λͺ¨λ λμλ₯Ό κ±°μΉκ³ λ€μ μ²μ λμλ‘ λμμ€λ λͺ¨λ κ²½λ‘ μ€ λΉμ©μ΄ κ°μ₯ μ κ² λλ κ²½λ‘μ λΉμ©μ ꡬνλ λ¬Έμ μ΄λ€.
π‘첫λ²μ§Έ μμ΄λμ΄
κ·Έλ₯ μμ΄μ ꡬν΄μ νλ©΄ μ΅λ 16! =20,922,789,888,000μΌλ‘ 1μ΄ μμ μ λ ν μ μλ€.
μ΄ λ¬Έμ λ 1μ£Όμ°¨ μ€ν°λμμ λ°°μ΄ λΉνΈλ§μ€νΉμ λν λ¬Έμ μκ³ , λ¬Έμ νμ΄ λ°©μμ κ±°μ λ€ λ°°μ μ΄μ DPμ λΉνΈλ§μ€νΉμΌλ‘ λ°λ‘ ν μ μμλ€.
λ¬Όλ‘ DP λμ λ°©μμ μ΄ν΄νκΈ° μν΄ μκ°μ΄ μ‘°κΈ κ±Έλ¦¬κΈ΄ νλ€.
π₯νμ΄π₯
dp[i][j]λ νμ¬ μμΉ iμ νμ¬κΉμ§ λ°©λ¬Ένλ μ μ λ€μ μ 보λ₯Ό λ΄μ j κ°μΌ λ, μμΌλ‘ νμν μν λΉμ©μ μ΅μκ°μ μλ―Ένλ€.
jκ° (1 << μ μ μ κ°μ) -1κ³Ό κ°μΌλ©΄ νμ¬ λͺ¨λ μ μ μ λ°©λ¬Ένλ€λ κ²μ μλ―Ένλ€.
κ° μ μ μ λν΄ μ λΆ λ°©λ¬Ένμ λμ μ΅μκ°μ μ°ΎμΌλ©΄ λλ―λ‘ μ λ΅μ dp[μ²μ μ μ ][1]μ΄λ€.
μλλ μ μΆν μ½λμ΄λ€.
#include <iostream>
#include <cmath>
using namespace std;
#define MAX 1000000000;
int dp[17][65537];
int w[17][17];
int n;
int solve(int cur, int visit) {
if (visit == (1 << n) - 1 && w[cur][0])
return w[cur][0];
if (dp[cur][visit]) return dp[cur][visit];
dp[cur][visit] = MAX;
for (int i = 1; i < n; i++) {
if (visit & (1 << i)) continue;
if (!w[cur][i]) continue;
dp[cur][visit] = min(dp[cur][visit], solve(i, visit | (1 << i)) + w[cur][i]);
}
return dp[cur][visit];
}
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> w[i][j];
}
}
cout << solve(0, 1);
}