글 읽기 - 반례 부탁드리겠습니다.

yonggi11 5년 전 0

혹시 이 문제에 반례를 댓글로 남겨주시면 정말 감사하겠습니다. 또는 제 소스 코드 중 잘못된 부분이 있을 시 피드백 해주시면 더욱 감사드리겠습니다.

즐거운 하루 보내세요 ^^..

#include <iostream>
#include <vector>

using namespace std;

int n,k;
int bt[1001]; // building time, 건물 짓는데 걸리는 시간.
vector<int> tailOf[1001]; //선행 건물 저장.
int dp[1001];

int search(int w){
    if(dp[w] != -1) return dp[w];
    if(tailOf[w].empty()){
        dp[w] = bt[w];
        return dp[w];
    }
    while(!tailOf[w].empty()){
        int tail = tailOf[w].back();
        tailOf[w].pop_back();
        if(w == tail) search(tail);
        else dp[w] = max(dp[w], search(tail) + bt[w]);
        
    }
    return dp[w];
}

int main(){
    int test_case,h,t,w;
    cin >> test_case;
    
    for(int i=0; i<test_case; i++){
        cin >> n >> k;
        
        for(int j=1; j<=n; j++){
            cin >> bt[j];
            dp[j] = -1;
            if(!tailOf[j].empty()) tailOf[j].clear();
        }
        
        for(int j=0; j<k; j++){
            cin >> t >> h;
            tailOf[h].push_back(t);
        }
        cin >> w;
        cout << search(w);
    }
}

djm03178 5년 전 2

테스트 케이스마다 개행 문자를 출력해야 합니다.

yonggi11 5년 전 0

@djm03178

친절한 답변 감사드립니다. 이런 실수를 했네요. 앞으로도 종종 잘부탁드립니다 ^^

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

문제

문제

출처

ICPC

반례 부탁드리겠습니다.

yonggi11 5년 전 0

djm03178 5년 전 2

yonggi11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말