[C] 백준 - 13305번: 주유소

4월 6일(목)-그리디 알고리즘(13305번)

13305번: 주유소

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- N-1개의 도로들의 길이는 road[100000]배열에, N개 도시의 주유소 가격은 gas[100000]배열에 입력받는다

- 일단 첫 번째 도시에서 두 번째 도시로 이동하려면 무조건 첫 번째 도시에서 주유를 해야한다

   따라서 최저기름값을 저장할 변수 min_gas의 초기값은 gas[1]으로 정해야한다

   또한 최종적으로 출력할 최소비용의 초기값은 gas[1] x road[1]으로 정해야한다

- 이후 두 번째 도시부터 나오는 기름값을 비교하며 최저기름값인 min_gas를 찾는다

- 이전에 누적된 비용 + ( min_gas x road[i] )를 해주며 최소비용을 갱신해준 뒤, 최종적으로 출력

 

-> 이 과정을 전체적으로 처음 생각해보니 동적 계획법과 다를바가 없는 것 같아서 최소비용은 dp[100000]에서 갱신

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

	// 수정 전ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
	long long min_gas = gas[1];
	for (int i = 2; i <= N - 1; i++)
	{
		if (min_gas > gas[i])
		{
			min_gas = gas[i];
		}
	}
	
	dp[1] = gas[1] * road[1];
	for (int i = 2; i <= N - 1; i++)
	{
		dp[i] = dp[i - 1] + min_gas * road[i];
	}
    
    	// 수정 후ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ    
    	long long min_gas = gas[1];
	dp[1] = gas[1] * road[1];
	for (int i = 2; i <= N - 1; i++)
	{
		if (min_gas > gas[i])
		{
			min_gas = gas[i];
		}
		dp[i] = dp[i - 1] + min_gas * road[i];
	}

1. 예제1번과 예제2번 모두 제대로된 출력값이 나오지만, 17점 부분성공

-> 작성한 코드를 다시 따라가보니,

    첫 번째 반복문을 통해서 전체 주유소를 돌며 min_gas를 최종적으로 찾고 난 뒤에

    두 번째 반복문에서 min_gas 값을 road[1]을 제외한 모든 거리에 곱하며 최소비용을 계산하고 있었다

    결국 최저기름값이 첫 번째 혹은 두 번째 주유소에서 나오는 경우를 제외하고는 잘못된 출력값이 나오는 상황

-> 예제1번은 2번째 주유소에서 최저기름값이 나왔고,

    예제2번은 모든 주유소에서의 기름값이 같았기에 예제를 통해서는 문제를 발견 못했었음

 

-> 따라서 하나의 반복문으로 통합하고 (각각의 당시 상황에서 최저기름값인 min_gas x road[i] )로 수정

-> 이를 통해서 최종적인 최저기름값이 나오기전까지는, 바로 다음 주유소까지의 거리를 이동할만큼만 주유를 하고

    만약 최저기름값을 발견하는 경우, 최저기름값을 그 이후의 남은 거리에 모두 곱하는 방향으로 구현

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

long long road[100000];
long long gas[100000];
long long dp[100000];

int main(void)
{
	int N;
	scanf("%d", &N);

	for (int i = 1; i <= N - 1; i++)
	{
		scanf("%lld", &road[i]);
	}
	for (int i = 1; i <= N; i++)
	{
		scanf("%lld", &gas[i]);
	}

	long long min_gas = gas[1];
	dp[1] = gas[1] * road[1];
	for (int i = 2; i <= N - 1; i++)
	{
		if (min_gas > gas[i])
		{
			min_gas = gas[i];
		}
		dp[i] = dp[i - 1] + min_gas * road[i];
	}

	printf("%lld", dp[N-1]);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ