20200522 프로그래머스 level 2 - 다리를 지나는 트럭

 오늘도 역시 예시를 먼저 들면서 시작하도록 하겠다.

 위의 예시를 보다시피 다리의 길이는 2, 그 다리는 10kg의 무게를 견딜 수 있다. 그리고 무게가 7, 4, 5, 6인 차량이 순서대로 지나간다.

 차로는 1차로만 존재하며, 시간 1에 1의 거리를 나갈 수 있다. 그럼 최소로 걸리는 시간은 몇인가를 구하는 문제이다.

 위의 예시를 보면 7kg인 차가 올라가면 뒤에있는 4kg의 차는 못 올라간다. 다리가 견딜 수 있는 무게는 10인데 7과 4가 합치면 11이기 때문이다.

 7이 다 지나가고, 4가 올라온다. 그 다음에 5가 올라온다. 4 + 5는 9이기 때문에 가능하다.

 5다음은 6인데 마찬가지로 둘의 크기 합이 11이기 때문에 5가 다 지나간 뒤에야 6이 지나갈 수 있다. 그렇게 해서 걸린 시간이 총 8이다.

 이 문제를 풀면서 주의해야할 점이 있다. 바로 다리 길이와 지나는 시간이 다르다는 것이다. 위의 시간을 자세히 보면 처음 7kg의 차량이 이동한 시간은 0부터 시작하여 총 4초의 시간이 걸렸다. 하지만 첫 시작 시간이 0이고, 앞 차가 다리를 지나가는 순간 바로 뒷차가 올라오므로 첫차를 제외한 처음 올라가는 시간은 의미가 없다. 거기다 첫 시간은 없다고 생각해도 무방하다.

 다음으론 마지막 시간이다. 위에서 보면 마지막에서 두번째인 6~7초가 끝난 뒤 모두 '다리를 지난 트럭'에 들어가야 끝나게 된다. 물론 이 또한 끝차만 신경쓰면 되긴 한다. 그래도 꼭 + 1을 해줘야 한다는 것을 잊지 말아야 한다.

 이 문제를 푸는 방법은 간단했다. 변수 벡터를 하나 만들어준다. 그리고 size는 트럭의 숫자만큼이고, 안에 들어가는 숫자는 모두 다리의 길이이다.

 트럭의 수만큼 for문을 돌려주고, 그 안에서 다리가 견딜 수 있는 무게가 몇대인지 또 찾는다. 거기에 해당하는 트럭들은 내가 만든 벡터에서 그만큼의 시간이 도무 빠져나가고, 그 시간은 return될 답에 += 된다.

 이것을 반복해주면 된다.

int solution(int bridge_length, int weight, vector truck_weights)

{

     int answer = 0;

     //각자 트럭이 지나가는 시간

     vector time;

     //초기값은 모든 트럭이 다리의 길이만큼 가지고 있다.

     for (int i = 0; i < truck_weights.size(); i++)

     {

          time.push_back(bridge_length);

     }

     //트럭의 개수만큼 계산해주면 됨

     for (int i = 0; i < truck_weights.size(); i++)

     {

          int sumWeight = truck_weights[i];

          int j = i + 1;

          //먼저 얼마큼이 한 묶음인지 확인해준다.

          for (j; j < truck_weights.size(); j++)

          {

                sumWeight += truck_weights[j];

               if (sumWeight > weight) break; }

               answer += time[i];

               for (int h = j - 1; h >= i; h--)

          {

          time[h] -= time[i];

          if (h == i) time[h]--;

          else

           {

                if (time[h] == 0) time[h]++;

          }

     }

}

//0번 인덱스차가 들어가는데 1초 걸리므로 //위에서 계산되지 못한 1을 더해준다.

return answer + 1;

}

 

말은 어렵게 한 감이 없지않아 있지만 속 내용은 살짝만 봐도 알만한 쉬운 내용이니 넘어가도록 하겠다.