https://school.programmers.co.kr/learn/courses/30/lessons/42583
*๋ฌธ์ ์ค๋ช
๋ค๋ฆฌ์ ๊ธธ์ด, ๋ค๋ฆฌ๊ฐ ๋ฒํธ ์ ์๋ ๋ฌด๊ฒ์ ์ต๋ ๊ฐ, ๋ฌด๊ฒ๋ฅผ ๋ด์ ํธ๋ญ vector๊ฐ ์ฃผ์ด์ง๋ค.
๋ชจ๋ ํธ๋ญ์ด ๋ค๋ฆฌ๋ฅผ ์ง๋ ๋ ๋ช์ด๊ฐ ๊ฑธ๋ฆฌ๋์ง๋ฅผ ๋ฐํํ๋ฉด ๋๋ค.
ํ๋ฒ์ ๋ค๋ฆฌ๋ฅผ ์ง๋๋ ํธ๋ญ ๊ฐ์๋ ๋ค๋ฆฌ์ ๊ธธ์ด๋ฅผ ๋์ ์ ์๊ณ ๋ค๋ฆฌ๊ฐ ๋ฒํธ ์ ์๋ ๋ฌด๊ฒ์ ์ต๋๊ฐ์ ๋๊ธธ ์ ์๋ค.
ํธ๋ญ์ด ๋ค๋ฆฌ๊ธธ์ด 1์ ์ง๋ ๋, 1์ด๊ฐ ์์๋๋ค. ๋ค๋ฆฌ๊ธธ์ด๊ฐ 2๋ผ๋ฉด 1์ด๋น 1์ฉ ์ง๋์ ๋ค ๊ฑด๋๋๋ฐ ์ด 3์ด์ ์๊ฐ์ด ํ์ํ๋ค.
*๋ฌธ์ ํด๊ฒฐ๋ฒ
๊ฑด๋์ผ ํ๋ ํธ๋ญ์ ๋ฆฌ์คํธ ํฌ๊ธฐ๋งํผ queue๋ฅผ ์์ฑํ๊ณ 0์ผ๋ก ์ฑ์๋๋ค.
queue์ ํ์ฌ ๋ค๋ฆฌ๋ฅผ ์ง๋๊ณ ์๋ ํธ๋ญ์ ๋ด๋๋ค.
๋ค์ ํธ๋ญ์ ๋ฌด๊ฒ๊ฐ ๋์์ ๊ฑด๋ ์ ์๋ ํธ๋ญ์ธ์ง ์ฒดํฌํ๋ค.
๋ฌด๊ฒ์ ํฉ์ด ๋์์ ๊ฑด๋ ์ ์๋ค๋ฉด 0์ queue์ ์ถ๊ฐํ๊ณ , ๋์์ ๊ฑด๋ ์ ์๋ค๋ฉด ๋ค์ ํธ๋ญ์ queue์ ๋ฃ๋๋ค.
*์์๋ ๊ฒ
๊ฑ ๋ฌธ์ ๊ฐ ์ ์ดํด๊ฐ ์๊ฐ์ ํ๋ฒ ๋ ํ์ด๋ณด๊ธฐ๋ฅผ...
*์ฝ๋
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0; //ํธ๋ญ์ด ์ง๋๊ฐ๋๋ฐ ๊ฑธ๋ฆฐ ์๊ฐ
int next_truck = 0; //๋ค์์ ์ด๋ํ ํธ๋ญ์ ๊ฐ๋ฆฌํค๋ ์ธ๋ฑ์ค
int weight_sum = 0; //๋ค๋ฆฌ ์์ ์ฌ๋ฆด ํธ๋ญ๋ค์ ๋ฌด๊ฒ ํฉ
queue<int> on_bridge; //๋ค๋ฆฌ ์์ ์๋ ํธ๋ญ๋ค์ ๋ฆฌ์คํธ
//๋งจ ์ด๊ธฐ ๋ค๋ฆฌ๋ฅผ ๋ค๋ฆฌ๊ธธ์ด ๋งํผ 0์ผ๋ก ์ด๊ธฐํ
for(int i = 0; i < bridge_length; i++){
on_bridge.push(0);
}
//๋ค๋ฆฌ ์๊ฐ ๋น์ด์์ง ์์ ๋์ ๋ฐ๋ณต๋ฌธ ์งํ
while(!on_bridge.empty()){
//์ด ๋๋ฆฌ๊ธฐ
answer++;
//๋ค๋ฆฌ ์ ์๋์ฐจ ๋ฌด๊ฒ๋ค์ ํฉ
weight_sum -= on_bridge.front();
//ํธ๋ญ ๊ฑด๋๊ธฐ OK
on_bridge.pop();
if(next_truck < truck_weights.size()){
//๋ค๋ฆฌ๊ฐ ๊ฒฌ๋ ์ ์๋ ๋ฌด๊ฒ๋ฅผ ๋์ง ์์ผ๋ฉด
if(weight_sum + truck_weights[next_truck] <= weight){
//๋ฌด๊ฒ ํฉ์ ๋ค์ ํธ๋ญ ๋ฌด๊ฒ๋ฅผ ๋ํจ
weight_sum += truck_weights[next_truck];
//๋ค๋ฆฌ ์์ ํธ๋ญ์ ์ฌ๋ฆผ
on_bridge.push(truck_weights[next_truck]);
//ํธ๋ญ ์ธ๋ฑ์ค ํ๋ ๋๋ ค์ฃผ๊ธฐ
next_truck++;
}
//๋ค๋ฆฌ๊ฐ ๊ฒฌ๋ ์ ์๋ ๋ฌด๊ฒ๋ฅผ ๋์๋ค๋ฉด ํธ๋ญ ๋์ 0์ ๋ฃ์
else on_bridge.push(0);
}
}
return answer;
}
'๐ Coding Test Study > Algorithm Problem' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++][Goorm][์ ๋ ฌ] ๋จ์ด์ฅ ๋ง๋ค๊ธฐ (1) | 2023.06.08 |
---|---|
[C++][Programmers][BFS/DFS] ์์ดํ ์ค๊ธฐ (0) | 2023.06.06 |
[C++][Programmers][์คํ/ํ] ์ฃผ์๊ฐ๊ฒฉ (0) | 2023.06.04 |
[C++][Programmers][์คํ/ํ] ํ๋ก์ธ์ค (0) | 2023.06.04 |
[C++][Programmers][์คํ/ํ] ๊ธฐ๋ฅ๊ฐ๋ฐ (0) | 2023.05.18 |