글 읽기 - 시간을 어떻게 더 줄일까요 63%

swjwpower 2년 전 0

dp[마지막 구매자][비트]{산 사람의 수, 총 가격} 으로 테이블을 짯는데 더 시간을 줄일 방법을 모르겠습니다...

근본부터 뜯어고쳐야 될까요

#pragma warning (disable:4996)
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

int artist[17][17], n;

pair <int, int> dp[17][34000];

pair <int, int> func(int idx, int cost, int bit, int sum, int cnt) {
	int i, j, tmp;
	pair <int, int>& ret = dp[idx][bit], data;

	if (ret.first != -1 && ret.second <= sum) return ret;

	ret.first = cnt;
	ret.second = sum;

	for (i = idx, j = 1; j < n; j++) {
		tmp = bit | (1 << j);
		if (cost <= artist[i][j] && tmp != bit) {
			data = func(j, artist[i][j], tmp, sum + artist[i][j], cnt + 1);
			if (ret.first == data.first && ret.second > data.second) ret = data;
			else if (ret.first < data.first) ret = data;
		}
	}

	return ret;
}

int main() {
	cin >> n;
	int i, j;

	for (i = 0; i < n; i++) {
		for (j = 0; j < (1 << n); j++) {
			dp[i][j].first = -1;
			dp[i][j].second = -1;
		}
	}

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			scanf("%1d", &artist[i][j]);
		}
	}

	cout << func(0, 0, 1, 0, 1).first;

}

pmn0001 2년 전 1

sum을 왜 구하시는건지 잘 모르겠습니다. 이유가 있나요?

swjwpower 2년 전 0

아 다시보니 sum을 구할 필요가 없엇네요 ㅋㅋ 그냥 cost값으로만 하면 될걸..

이걸 고치니 79퍼에서 시간초과가 낫고 함수 중간에 cnt == n일 경우 exit을 해줘서 AC나왔습니다. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간을 어떻게 더 줄일까요 63%

swjwpower 2년 전 0

pmn0001 2년 전 1

swjwpower 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말