글 읽기 - 용감한 용사 진수 질문이여..

cheetose 6년 전 0

d[i][j]=d[N번째 적][죽인 적] 이라고 하고

d[i][j] 테이블을 채울 때 d[k][j-1] (k=j-1 to i-1)과 d[k][j] (k=j to i-1)를 비교해가면서 stat.total이 최소가 되는 값으로 계속 업데이트 해줬는데 잘못된 방법인가요..? 혹시 이게 잘못된 방법이라면 어떤 식으로 접근해야할지 힌트라도 주실 수 있나요..??

#include<cstdio>
#include<algorithm>
#define INF 5000000
using namespace std;
struct Stat {
	int STR, INT, DEX, total;
	Stat(int s=0, int i=0, int d=0)
	{
		STR = s, INT = i, DEX = d, total = s+i+d;
	}
};
Stat S[101];
Stat d[101][101];
int main()
{
	freopen("input.txt", "r", stdin);
	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++)
			d[i][j] = Stat(INF, INF, INF);
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		S[i] = Stat(x, y, z);
	}
	for (int i = 1; i <= n; i++)
	{
		int nows = S[i].STR, nowd = S[i].DEX, nowi = S[i].INT,nowt=S[i].total;
		for (int j = 1; j <= i; j++)
		{
			for (int k = j-1; k < i; k++)
			{
				int ss=d[k][j - 1].STR,dd=d[k][j-1].DEX,ii=d[k][j-1].INT;
				int ns = max(nows, ss), nd = max(nowd, dd), ni = max(nowi, ii);
				int nt = ns + nd + ni;
				if (d[i][j].total > nt) d[i][j] = Stat(ns, ni, nd);
			}
			for (int k = j; k < i; k++)
			{
				int ss = d[k][j].STR, dd = d[k][j].DEX, ii = d[k][j].INT;
				int nt = ss + dd + ii;
				if (d[i][j].total > nt) d[i][j] = Stat(ss, ii, dd);
			}
		}
	}
	printf("%d",d[n][m].total);
}
// freopen("input.txt", "r", stdin);

lyzqm 6년 전 0

저도 이렇게 접근했는데 계속 틀렸다고 나오네요 ㅎㅎ;;

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, M;
int save[111][4];
int dp[111][111][5];
int get(int idx, int num) {
	int ret = 0;
	int a = max(save[idx][1], dp[idx + 1][num + 1][1]);
	int b = max(save[idx][2], dp[idx + 1][num + 1][2]);
	int c = max(save[idx][3], dp[idx + 1][num + 1][3]);
	ret += a - dp[idx + 1][num + 1][1];
	ret += b - dp[idx + 1][num + 1][2];
	ret += c - dp[idx + 1][num + 1][3];
	/*printf("[%d,%d] : %d %d %d\n", idx,num,save[idx][1], save[idx][2], save[idx][3]);
	printf("%d %d %d\n\n", dp[idx + 1][num + 1][1], dp[idx + 1][num + 1][2], dp[idx + 1][num + 1][3]);*/
	return ret;
}
void solve(int idx, int num) {
	if (num == M) {
		dp[idx][num][0] = 1;
		dp[idx][num][1] = save[idx - 1][1];
		dp[idx][num][2] = save[idx - 1][2];
		dp[idx][num][3] = save[idx - 1][3];
		dp[idx][num][4] = save[idx - 1][1] + save[idx - 1][2] + save[idx - 1][3];
		return;
	}
	if (idx >= N) {
		dp[idx][num][0] = 1;
		dp[idx][num][1] = INF / 3;
		dp[idx][num][2] = INF / 3;
		dp[idx][num][3] = INF / 3;
		dp[idx][num][4] = INF;
		return;
	}
	if (dp[idx][num][0] != -1) return;
	dp[idx][num][0] = 1;
	dp[idx][num][1] = dp[idx][num][2] = dp[idx][num][3] = 0;
	dp[idx][num][4] = INF;
	solve(idx + 1, num);
	if (dp[idx][num][4] > dp[idx + 1][num][4]) {
		dp[idx][num][1] = dp[idx + 1][num][1];
		dp[idx][num][2] = dp[idx + 1][num][2];
		dp[idx][num][3] = dp[idx + 1][num][3];
		dp[idx][num][4] = dp[idx + 1][num][4];
	}
	solve(idx + 1, num + 1);
	if (dp[idx][num][4] > dp[idx + 1][num + 1][4] + get(idx, num)) {
		dp[idx][num][4] = dp[idx + 1][num + 1][4] + get(idx, num);
		dp[idx][num][1] = max(dp[idx + 1][num + 1][1], save[idx][1]);
		dp[idx][num][2] = max(dp[idx + 1][num + 1][2], save[idx][2]);
		dp[idx][num][3] = max(dp[idx + 1][num + 1][3], save[idx][3]);
	}
}
int main() {
	memset(dp, -1, sizeof dp);
	scanf("%d%d", &N, &M);
	for (int n = 0;n < N;n++) scanf("%d%d%d", &save[n][1], &save[n][2], &save[n][3]);
	solve(0, 0);
	printf("%d\n", dp[0][0][4]);
	return 0;
}

ainch96 6년 전 0

능력치 좌표 압축 시킨 다음 ( sort + binary search ) , for문 3번 돌면서, ( i,j,k : 각각의 능력치 인덱스 값 )

각 구간안에 들어 있는 병사의 수가 K보다 이상이면, 업데이트 해주는 식으로 하면...

( 병사의 수는 dp 전처리를 통해서 O(1) 만에 구하고 )

시간 : O(n ^ 3 ) / 공간 : O ( n ^ 3 ) 만에 구할 수 있을 것 같습니다.

반례가 당장 떠오르지는 않지만 분명이 있을 것 같습니다. 능력치 3개의 합이 더 크더라도

뒤에 오는 값을 포괄하기에 유리한 케이스가 존재할 것 같습니다. 지금 학교 실습 마치면 만들어 보겠습니다.

cheetose 6년 전 0

으... 제가 멍청해서 능력치 좌표 압축시킨다는 말을 이해를 못하겠어요 ㅠㅠ

jason9319 6년 전 1

좌표압축 기법은 이 문제의 경우 수의 범위가 0~100만이므로 모든 힘 민첩 지능에 대해 100만 ^3 으로 탐색을 하면 너무 많은 시간이 걸리므로

입력에 등장하는 숫자들만 가지고 탐색을 하는겁니다.

수의 범위는 100만이지만 나올 수 있는 최대 수는 100개 밖에 안되기 때문이죠 따라서 100 ^3으로 가능한 모든 답의 후보를 만들 수 있습니다.

jason9319 6년 전 1

예를들면 이런식으로 입력을 벡터들에 저장하여 저 수들만 확인해주는걸 아마 좌표압축이라고 부를겁니다. (보통은 등장하는 수에 고유의 번호를 매겨주기 위해 사용됩니다.)

for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &d[i].first, &d[i].second.first, &d[i].second.second);
		x.push_back(d[i].first);
		y.push_back(d[i].second.first);
		z.push_back(d[i].second.second);
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	sort(z.begin(), z.end());
	x.erase(unique(x.begin(), x.end()), x.end());
	y.erase(unique(y.begin(), y.end()), y.end());
	z.erase(unique(z.begin(), z.end()), z.end());

cheetose 6년 전 2

아아아 자세한 설명 너무 감사드립니다 ㅠㅠ 다시 한 번 풀어볼게요!! 덕분에 새로 하나 배웠네요 ㅎㅎ

ainch96 6년 전 1

헐 너무 늦게 봤네요 죄송니다.

대신 친절하게 설명해주신

jason9319

님 감사합니다.

cheetose 6년 전 2

음.. 한번 O(n^4)로 제출해봤는데 왜 매우 여유롭게 AC가 나오는지 모르겠네요.. 암튼 덕분에 풀긴 풀었네요 ㅋㅋㅋㅋㅋㅋ 두분 다 너무 감사합니다

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

문제

문제

출처

ICPC

용감한 용사 진수 질문이여..

cheetose 6년 전 0

lyzqm 6년 전 0

ainch96 6년 전 0

cheetose 6년 전 0

jason9319 6년 전 1

jason9319 6년 전 1

cheetose 6년 전 2

ainch96 6년 전 1

jason9319

cheetose 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말