1005 ACM craft

처음 짜서 런타임에러 + 논리적 오류가 발생한 코드

#include <iostream>

#include <vector>

using namespace std;

int D[1001];

int XY[1001][1001];

int DP[1001];

int main(){

int T = 0, N = 1, K = 1, X, Y, W;

cin >> T;

while (T--)

{

int ans = 0;

cin >> N >> K;

for (int i = 1; i <= N; i++)

{

cin >> D[i];

}

for (int i = 1; i <= K; i++)

{

cin >> X >> Y;

XY[X][Y] = 1;

}

cin >> W;

DP[1] = D[1];

for (int i = 1; i <= N;){

vector<int> V;

for (int j = 1; j <= N; j++){

if (XY[i][j] == 1){

V.push_back(j);   // 1번 건물을 시작으로 연결된 그 다음 건물을 찾습니다.

}

}

int max = 0, z = 0;

for (int k = 0; k < V.size(); k++){

if (max < D[V[k]]){

max = D[V[k]]; z = k + 1;  // 그 다음 건물 중에서 시간이 가장 오래 걸리는 건물을 선정합니다.

}

}

DP[V[z - 1]] = DP[i] + max; // 가장 오래 걸리는 시간과 직전의 건물에 걸리는 시간을 더합니다.

i = V[z - 1];

if (i == W) break;

}

cout << DP[W] << endl;

}

return 0;

}

솔직히 왜 틀린지 모르겠다. 문제를 잘 이해하지 못해서 그런가.. ?

구글링을 통해 재귀 호출방법으로 맞은 코드.

내가 생각했던 것의 반대 방향으로 한 것인데... 물론 내가 짠 코드가 틀린건 분명할것..

재귀함수가 헷갈릴 때, 아래 코드를 계속 생각해봐야겠다.

#include <iostream>

#include <algorithm>

using namespace std;

int DP[1001];

int M[1001][1001], D[1001];

int solve(int W, int N) {

if (DP[W] > 0) return DP[W];

int result = 0;

for (int i = 1; i <= N; i++) {

if (M[i][W] == 1) {

result = max(result, solve(i, N));

}

}

return DP[W] = result + D[W];

}

int main() {

int T;

//scanf("%d", &T);

cin >> T;

for (int i = 0; i < T; i++) {

int N, K, W;

for (int j = 0; j < 1001; j++) D[j] = DP[j] = 0;

for (int j = 0; j < 1001; j++) for (int k = 0; k < 1001; k++) M[j][k] = 0;

//scanf("%d %d", &N, &K);

cin >> N >> K; 

for (int j = 1; j <= N; j++) cin >> D[j];

for (int j = 0; j < K; j++) {

int x, y;

//scanf("%d %d", &x, &y);

cin >> x >> y;

M[x][y] = 1;

}

//scanf("%d", &W);

cin >> W;

printf("%d\n", solve(W, N));

}

system("pause");

return 0;

}