3056 007

이것도 이전에 코딩은 다 해놨는데 결과값 배열이 너무 커서 메모리초과가 나는 문제가 있었다.

double d[20][1048575];

이녀석이 문제였는데 지금 생각해보니 해법은 간단하다. 어차피 한단계 전의 것만 참조하므로 [2][]로 선언해 주고 %2로 구분하면 되는것.

※ 소수점 자리 신경안쓰다가 한번 틀렸다. 정신차리자

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, a[21][21];
double d[2][1048575];
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    int rm = 1 << n;
 
    for (int i = 0; i < n; i++) d[0][1 << i] = a[0][i];
 
    for (int i = 0; i < n - 1; i++) for (int j = 0; j < rm; j++) {
        if (d[i % 2][j]) {
            for (int k = 0; k < n; k++) {
                if ((j&(1 << k)) == 0)
                    d[(i + 1) % 2][j | (1 << k)] = max(d[(i + 1) % 2][j | (1 << k)], d[i % 2][j] * a[i + 1][k] / 100);
            }
        }
    }
 
    printf("%.10f\n", d[(n - 1)%2][rm - 1]);
    return 0;
}