백준 16399번 드라이브

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

같은 학교 학우이신 Green55님(https://blog.naver.com/pasdfq/221395443305)의 도움으로 풀 수 있었던 문제였습니다.

정해는 현재 보유하고 있는 기름의 양으로 갈 수 있는 주유소들 중 제일 멀리 있는 주유소에 가서 가득 채우고 움직이는 형식으로 그리디하게 접근하는 방식이라고 합니다.

하지만 출제진의 의도와는 다르게 대부분의 사람들은 DP로 풀었다고 합니다.

알고리즘은 아래와 같습니다.

1. 주유소의 위치가 주어진 것이 아니기 때문에 부분합으로 주유소의 위치를 저장해야합니다.

2. idx 번째 주유소에서 gas만큼의 기름이 있을 때 아래와 같이 세 가지 조치를 취할 수 있습니다.

i) 현재 지점에서 기름을 꽉 채운다

ii) 특정 지점에 도착할만큼만 기름을 채운다

iii) 기름을 채우지 않는다

3. 2번의 i), ii), iii)의 조건을 일일이 확인하면서 움직이면 최소 값을 구할 수 있습니다.

4. 물론 3번에서 마지막 주유소까지 도달하지 못하면 -1을 출력해야합니다.

#include <iostream>

#include <algorithm>

#include <cstring>

#include <climits> //LLONG_MAX

using namespace std;

 

const int MAX = 1000 + 2;

 

int C, E, D, N; //용량, 연비, 거리, 주유소 개수

long long dist[MAX], price[MAX];

long long cache[MAX][500 + 1]; //idx, gas

 

long long minPrice(int idx, int gas)

{

        //도착

        if (idx == N + 1)

                 return 0;

       

        long long &result = cache[idx][gas];

        if (result != -1)

                 return result;

 

        result = LLONG_MAX;

        //기름을 꽉 채워도 다음 지점으로 갈 수 없다

        if (C < (E * (dist[idx + 1] - dist[idx])))

                 return result;

        //기름을 꽉 채우고 다음 지점으로

        result = min(result, price[idx] * (C - gas) + minPrice(idx + 1, C - E * (dist[idx + 1] - dist[idx])));

 

        //i번째 지점까지

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

        {

                 //기름은 아무리 채워도 한번에 갈 수 없는 경우

                 int gasUsed = E * (dist[i] - dist[idx]);

                 if (gasUsed > C)

                         break;

 

                 //기름이 충분하면 채우지 않고 그냥 간다

                 if (gasUsed <= gas)

                         result = min(result, minPrice(i, gas - gasUsed));

                 else

                         result = min(result, (gasUsed - gas) * price[idx] + minPrice(i, 0));

        }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> C >> E >> D >> N;

 

        //주유소 존재하지 않는 경우

        if (!N)

        {

                 if (D*E <= C)

                         cout << 0 << "\n";

                 else

                         cout << -1 << "\n";

                 return 0;

        }

 

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

        {

                 int d;

                 cin >> d;

 

                 dist[i] = dist[i - 1] + d;

        }

        dist[N + 1] = D; //마지막 주유소 거리도 처리

 

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

                 cin >> price[i];

       

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

        long long result = minPrice(0, C);

        if (result == LLONG_MAX || result < 0)

                 cout << -1 << "\n";

        else

                 cout << result << "\n";

        return 0;

}

 

 

개발환경:Visual Studio 2017

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