[Level2/c++] 다리를 지나는 트럭

문제

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스

풀이

트럭을 적재할 다리, 즉 벡터 vector<pair<int,int>> load; 를 선언합니다.

first에는 트럭이 이동한 거리, second에는 트럭의 무게를 담아줍니다.

 

1. 다리 위 맨 앞에 있는 트럭이 다리길이만큼 이동했다면

벡터에서 제거하고 (다리 위 트럭의 총 무게) -= (맨 앞에 있던 트럭의 무게) 를 해줍니다.

2. (다리 위 트럭의 총 무게) + (다음 트럭의 무게) <= (다리가 버틸수있는 무게) 라면 벡터에 추가해줍니다.

3. 다리에 있는 트럭들을 전부 1칸씩 이동시키고

4. 시간+=1을 해줍니다.

5. 모든 트럭이 다리를 지나갈때까지 반복

 

코드(시간복잡도 O(n^2)) *n^2가 아니라면 알려주세요. 감사합니다(--)(__)*