-
[Algorithm] 프로그래머스 C++ : 다리를 지나는 트럭Algorithm 2020. 8. 7. 01:22
https://programmers.co.kr/learn/courses/30/lessons/42583#
되게 헤맸던 문제..
그냥 봤을땐 쉬워보이는데 큐에 넣으면서 초를 세는게 헷갈린다.
첫번째 포인트는, while(1)을 해놓고 다리에 올라갈 수 없는 트럭이 나오면
그냥 0을 큐에 삽입해서 초가 증가할 수 있게 해주는 것!
두번째 포인트는, 다리에 올라갈 수 있는 트럭이 꽉 차서 큐의 맨 앞 트럭을 뺌과 동시에
다리에 올라가 있는 총 트럭의 무게가 감소하고 그와 동시에 다시 새로운 트럭이 삽입된다!!
break의 조건은 트럭의 인덱스인데
다 삽입됐을 때, 마지막 트럭은 이제 막 다리에 올라온 것이므로
bridge_length만큼 초를 더해줘야 한다.
Code
#include <string> #include <vector> #include <iostream> #include <queue> using namespace std; int solution(int bridge_length, int weight, vector<int> truck_weights) { int answer = 0; int sum = 0; int idx = 0; queue<int> q; while(1) { if(idx == truck_weights.size()) { answer += bridge_length; break; } answer++; int tmp = truck_weights[idx]; if(q.size()==bridge_length) { sum -= q.front(); q.pop(); } if(sum + tmp <= weight) { q.push(tmp); sum += tmp; idx++; } else { q.push(0); } } return answer; }
'Algorithm' 카테고리의 다른 글
[Algorithm] 프로그래머스 C++ : 더 맵게 (0) 2020.08.10 [Algorithm] 프로그래머스 C++ : 프린터 (0) 2020.08.09 [Algorithm] 프로그래머스 C++ : 기능개발 (0) 2020.08.06 [Algorithm] 프로그래머스 C++ : 주식가격 (0) 2020.08.05 [Algorithm] 프로그래머스 C++ : 베스트앨범 (0) 2020.07.14