[백준][1446번][수학] 지름길

지름길

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

<코드>

#include <stdio.h>
 
int Min(int a, int b){
    return a < b ? a : b;
}
 
// 지름길에 대한 가지고 있는 객체
struct quickRoad{
    int first;
    int last;
    int value;
};
 
int main(void){
 
    int shortroad_num, totalroad;
    int road[10000] = { 0, };
    int count = 0;
    int back = 0;
    quickRoad quickroad[10001];
    
    
    scanf("%d %d", &shortroad_num, &totalroad);
 
    for (int i = 0; i < shortroad_num; i++){
        quickRoad temp;
        scanf("%d %d %d", &temp.first, &temp.last, &temp.value);
        quickroad[i] = temp;
    }
 
    //--------------------------------------
    //            버블 소트로 정렬
    //--------------------------------------
    for (int i = 0; i < shortroad_num; i++)
    {
        for (int j = i; j < shortroad_num; j++){
            if (quickroad[i].first > quickroad[j].first){
                quickRoad temp;
                temp = quickroad[j];
                quickroad[j] = quickroad[i];
                quickroad[i] = temp;
            }
        }
    }
 
    //---------------------------------------------------
    //            행렬 
    //---------------------------------------------------
 
    //---------------------------------------------------
    //
    //        0부터 끝까지 차근차근 한칸씩 진행하는데 
    //
    //        지름길을 만나면 현재의 값과 지름길의 값을 합쳐서 그 지름길의 끝나는 곳에 저장한다.
    //
    //        이미 지름길이 왔던 길을 만나면 실제로 가는 길과 지름길로 왔던 값과 비교해서 적은값을 저장한다.
    //
    //---------------------------------------------------
 
    while (count != totalroad){
        if (quickroad[back].first == count){
            if (quickroad[back].last <= totalroad)
            {
                if (road[quickroad[back].last] != 0)
                    road[quickroad[back].last] = Min(road[count] + quickroad[back].value, road[quickroad[back].last]);
                else
                    road[quickroad[back].last] = road[count] + quickroad[back].value;
            }
            back++;
        }
        else{
            if (road[count + 1] != 0)
                road[count + 1] = Min(road[count + 1], road[count] + 1);
            else
                road[count + 1] = road[count] + 1;
            count++;
        }
 
    }
    
    //-------------------------------------------
    //            출력
    //-------------------------------------------
 
    printf("%d\n", road[totalroad]);
 
    return 0;
}

<문제 푼 요령>

 1.  여기서 중요한건 역주행을 못한다게 중요하다. 앞만보고 가기 때문에 한번의 탐색으로 끝낼 수 있다.

 2.  지름길에 대한 객체를 새로 만들고 그에 대한 객체를 배열에 저장한 후 버블 소트 시작점이 낮은 순으로 정렬한다.

 3.  0 부터 시작해서 차근차근하게 한칸씩 진행한다.

 4.  지름길이 시작점인 곳에 도착하면 현재의 값과 지름길로 갔을때의 값을 더해서 지름길이 나오는 곳에 값을 넣어준다.

 5.  차근차근하게 가다가 지름길이 나온점과 만나면 지름길에서 나온 값과 내가 차근히 왔던 값을 비교해서 작은값을 넣어준다.

 6.  반복한다.