글 읽기 - 이 두 코드 똑같은거 아닌가요?

xkdlaldfjtnl 3년 전 1

안녕하세요 N번에서 1번으로 가나 1번에서 N번으로 가나 똑같은 거 아닌가요?

그러니깐 양방향 간선이 아니라서 안된다고 생각하실텐데 제 말은 N번으로 향하는 간선이 있는 방향으로 짜면 똑같은거 같아서 질문을 드립니다.

제 머릿속 논리는 두 케이스는 같고, 밑에 코드도 차이가 없게 짠 것 같아서 결과도 차이가 없어야 할 것 같은데

1->N 으로 top down은 AC

N->1 으로는 WA가 뜹니다. 왜 그럴까요?

AC코드

#include <iostream>
#include <algorithm>
#include <cstring> 
using namespace std;
#define MAX 305
#define INF 987654321

int N, M, K;
int cost[MAX][MAX];
int dp[MAX][MAX]; 

int solve(int idx, int num){
	if (idx == N)
		return 0;
	if (num == M)
		return -INF;
	int &ret = dp[idx][num];
	if (ret != -1)
		return ret;
	for (int to = idx + 1; to <= N; to++)
		if (cost[idx][to])
			ret = max(ret, cost[idx][to] + solve(to, num + 1));
	return ret;
}



int main(){
	cin >> N >> M >> K;

	for (int i = 0; i < K; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		cost[a][b] = max(cost[a][b], c);
	}

	memset(dp, -1, sizeof(dp));
	cout << solve(1, 1);
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////


WA코드

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 305
#define INF 987654321

int N, M, K;
int dp[MAX][MAX];
int cost[MAX][MAX];

int solve(int idx, int num) {
	if (idx == 1) {
		return 0;
	}
	if (num == M)return -INF;
	int &ret = dp[idx][num];
	if (ret != -1)
		return ret;
	for (int to = 1; to < idx; to++) {
		if(cost[idx][to])
			ret = max(ret, cost[idx][to] + solve(to, num + 1));
	}
	return ret;
}

int main() {

	cin >> N >> M >> K;

	for (int i = 0; i < K; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		cost[b][a] = max(cost[b][a], c); // 이 부분을 다르게 짰음 
	}
	memset(dp, -1, sizeof(dp));
	cout << solve(N, 1);
}

djm03178 3년 전 3

정답을 받은 코드도 틀린 코드인데 데이터가 약해서 통과된 것 같습니다. 틀린 이유는 같습니다.

다음은 위쪽 코드가 틀리는 반례입니다.

3 3 2
1 2 3
1 3 1

정답: 1
이 코드의 출력: 2

xkdlaldfjtnl 3년 전 0

감사합니다. 더 열심히 해야겠네요 제 눈에는 반례가 도저히 보이지 않았었는데 감사합니다.

djm03178 3년 전 1

https://www.acmicpc.net/board/... 에 데이터 추가 요청을 올렸습니다.

xkdlaldfjtnl 3년 전 0

반례덕분에 재귀 작동방식도 좀 더 이해한 것 같습니다.

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

문제

문제

출처

ICPC

이 두 코드 똑같은거 아닌가요?

xkdlaldfjtnl 3년 전 1

djm03178 3년 전 3

xkdlaldfjtnl 3년 전 0

djm03178 3년 전 1

xkdlaldfjtnl 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말