[C 백준] 실버 4/ 13305번 주유소

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

 

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
 
long long road[100000];
long long cost[1000000];
long long dp[1000000];
 
int main() {
    
    int num;
    scanf("%d", &num);
 
    
    for (int i = 0; i < num - 1; i++) {
        scanf("%d", &road[i]);
    }
 
    
    for (int i = 0; i < num; i++) {
        scanf("%d", &cost[i]);
    }
 
    dp[0] = road[0] * cost[0];
    long long minPrice = cost[0];
    
    for (int i = 1; i < num-1; i++) {
        
        
        if (cost[i] < minPrice) {
            minPrice = cost[i]; //그래야 2랑 4랑 비교했을때 여전히 2가 min이 됨
        }
        dp[i] = dp[i - 1] + road[i] * minPrice;
        
    }
 
 
    
    
    printf("%ld\n", dp[num-2]);
 
 
 
    
    
}

 

그리디 문제인데 dp를 사용하면 시간초과없이 풀어낼 수 있다.

 

17점짜리 코드 

처음 풀었을 때는 17점을 맞았다.ㅋㅋㅋㅋ 문제를 푸는 아이디어는 대강 맞은 것 같긴하다.

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
 
 
int main() {
    
    int num;
    scanf("%d", &num);
 
    int* road = (int*)malloc(sizeof(int) * num-1 );
    for (int i = 0; i < num - 1; i++) {
        scanf("%d", &road[i]);
    }
 
    int* cost = (int*)malloc(sizeof(int) * num);
    for (int i = 0; i < num; i++) {
        scanf("%d", &cost[i]);
    }
 
    int* dp = (int*)malloc(sizeof(int) * num );
    
    for (int i = 0; i < num-1; i++) {
        if (i == 0) {
            dp[i] = road[i] * cost[i];
        }
        else if (i > 0) {
            int a = road[i] * cost[i - 1];
            int b = road[i] * cost[i];
            if (a <=b) {
                dp[i] = dp[i - 1] + a;
            }
            else if(b<a){
                dp[i] = dp[i - 1] + b;
            }
        }
        
    }
 
    
    
    printf("%d\n", dp[num-2]);
 
 
 
    
    
}

아이디어는 대략 이런느낌이다.

 

그런데 28번째줄부터 36번째줄까지가 너무 불필요한 코드가 많고 얘때문에 17점을 맞은 것 같았다.

 

그래서 dp[0]=cost[0]*road[0]으로 미리 지정해두고 minPrice도 cost[0]으로 지정한다.

그러면 minPrice값은 5이다.

for문을 돌면서 cost[i]가 minPrice보다 작으면 minPrice가 cost[i]가 된다.

 

5는 2보다 크기에 minPrice는 2가 될거고

4또한 2보다 크기에 minPrice는 여전히 4가 될 것이다.

그래서 위 사진의 경우 18이 최솟값이 된다.!!