백준 2157번 여행

문제 링크입니다: https://www.acmicpc.net/problem/2157

비교적 낮은 정답률인데도 불구하고 한번에 AC를 받아 기분 좋았던 DP 문제였습니다.

현재 위치한 도시와 해당 도시가 몇 번째 방문하는 도시인지를 표시하며 메모이제이션을 하면 되는 문제였습니다.

기내식을 입력받을 때 한 도시에서 다른 도시로 가는 비행기가 여러대 있을 수 있기 때문에 제일 맛있는 기내식을 제공하는 비행기를 채택하는 것이 핵심이였습니다.

기저 사례는 도시를 M번 거쳤는데 N번째 즉, 도착지점에 도달 못하는 경우이고 M번 이내에 N번째 도시를 방문하면 조건이 성립됩니다.

코드 자체는 어렵지 않기 때문에 코드를 보시면 쉽게 이해가 가실거라고 생각됩니다!

**수정**

해당 코드는 재채점 결과 틀림 처리가 되었고 새로 작성한 코드는 링크를 참고해주세요.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 300 + 1;

const int INF = 987654321;

 

int N, M, K;

int dist[MAX][MAX];

int cache[MAX][MAX]; //해당 도시, 몇번 방문?

 

int maxTaste(int idx, int visit)

{

        //기저 사례

        if (visit == M && idx != N)

                 return -INF;

        //조건 성립

        if (idx == N)

                 return 0;

 

        int &result = cache[idx][visit];

        if (result != -1)

                 return result;

 

        result = 0;

        //갈 수 있는 곳이면

        for (int to = idx + 1; to <= N; to++)

                 if (dist[idx][to])

                         result = max(result, dist[idx][to] + maxTaste(to, visit + 1));

 

        return result;

}

 

int main(void)

{

        cin >> N >> M >> K;

 

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

        {

                 int city1, city2, taste;

                 cin >> city1 >> city2 >> taste;

 

                 //city1 -> city2 제일 맛있는 기내식을 채택

                 dist[city1][city2] = max(dist[city1][city2], taste);

        }

 

        memset(cache, -1, sizeof(cache));

        cout << maxTaste(1, 1) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~