글 읽기 - 왜 몇번만에 갔는지 세줘야하는거죠?

nisroeld99 7년 전 0

ㅇㅕ행 문제풀다가 궁금한 점이 있습니다

처음에는 d[i] // i 에서 출발해서 목적지 (m)에 도착했을 때까지 얻을 수 있는 최대 기내식 만족도로 잡았는데

답변풀이보니까 d[i][j] // j 는 횟수로 잡으셨더라고요

이해가 잘 안가는데 왜 저 변수가 필요한지 궁금합니다.

제 코드 첨부합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;
typedef pair<int,int> ii;
const int inf = 987654321;
typedef long long ll ;
vector<ii> g[333];

int n , m ,k;
int d[333];  // d[i]  i부터 ~ n까지 최대한 얻을 수 있는 만족도
int go (int now ){
    if (now == n ) return 0 ;
    int &ret =  d[now];
    if ( ret != -1 ) return ret ;
    ret = 0 ;
    for (auto x : g[now]){
        if ( x.second < now) continue;
        ret = max (ret, x.first +go ( x.second) );
    }
    return ret ;
}

int main(){
    memset (d, -1,sizeof(d));
    scanf("%d%d%d",&n,&m,&k);
    for (int i = 0 ; i< k ;i++){
        int from ,to ,cost ;
        scanf("%d%d%d",&from, &to ,&cost );
        if (from >= to ) continue;
        g[from].push_back(ii(cost, to ));
    }
//    for (int i = 0 ; i<= m ;i++){
//        sort(g[i].begin() ,g[i].end() , greater<ii> () ) ;
//    }
//    
    printf("%d\n",go(1));
    
    
}

nisroeld99 7년 전 0

문제를 잘못읽었습니다

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

문제

문제

출처

ICPC

왜 몇번만에 갔는지 세줘야하는거죠?

nisroeld99 7년 전 0

nisroeld99 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말