백준 4883번 삼각그래프

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

문제 정답률에 비해 쉬웠던 DP 문제였습니다.

핵심은 4가지 방향을 고려해주는 문제였습니다: 오른쪽, 왼쪽 아래, 아래, 오른쪽 아래

이 때, 범위를 벗어나는 경우 INF를 반환하게 하여 최소 비용을 찾게 해주면 쉽게 정답을 찾을 수 있는 문제였습니다.

방심하고 문제 대충 읽다가 오른쪽을 고려안해서 정답률 하락에 보탬을 했던 것은 함정...

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100000;

const int INF = 987654321;

 

int N;

int graph[MAX][3];

long long cache[MAX][3];

 

long long minCost(int idx1, int idx2)

{

        //기저 사례: 범위 초과할 경우

        if (idx1 >= N || idx2 < 0 || idx2>2)

                 return INF;

        //도착점에 도착했을 경우

        if (idx1 == N - 1 && idx2 == 1)

                 return graph[idx1][idx2];

       

        long long &result = cache[idx1][idx2];

        if (result != -1)

                 return result;

 

        //총 네 방향으로 갈 수 있다: 오른쪽, 왼쪽 아래, 아래, 오른쪽 아래

        result = graph[idx1][idx2] + min(minCost(idx1, idx2+1), min(minCost(idx1 + 1, idx2 - 1), min(minCost(idx1 + 1, idx2), minCost(idx1 + 1, idx2 + 1))));

        return result;

}

 

int main(void)

{

        int K = 1;

        while (1)

        {

                 cin >> N;

                 if (N == 0)

                         break;

                

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

 

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

                         for (int j = 0; j < 3; j++)

                                 cin >> graph[i][j];

 

                 cout << K++ << ". "<< minCost(0, 1) <<endl;

        }

        return 0;

}

 

개발환경:Visual Studio 2017

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