알고리즘
BOJ 13335: 트럭
minbear
2023. 5. 1. 22:23
#BOJ 13335: 트럭
13335번: 트럭
입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트
www.acmicpc.net
#풀이
1. 트럭이 다리를 지나가는데 다리위에 있는 트럭의 무게의합은 다리의 최대무게 보단 안이어야 한다.
2. 트럭은 차례대로 지나가야 한다.
이렇게 하여 다리에 있는 트럭의 무게를 더하고 남은 무게에 들어갈 수 있으면 다리에 올리게 구현하였다.
#코드
#include<iostream> //#incldue<bits/stdc++.h>
#include<queue>
using namespace std;
int n, w, L;
int truck[1001];
queue<int> success;
int ans;
int bridge[102]; // 다리에 있는 트럭의 인덱스
void func1() {
for (int i = w; i >= 1; i--) {
bridge[i + 1] = bridge[i];
}
bridge[1] = 0;
if (bridge[w + 1] != 0)
{
L = L + truck[bridge[w + 1]];
success.push(bridge[w + 1]);
bridge[w + 1] = 0;
}
}
void func() {
for (int i = 1; i <= n; i++) {
if (i == 1) {
bridge[1] = 1;
L = L - truck[1];
ans++;
continue;
}
func1();
if (L - truck[i] >= 0) {
bridge[1] = i;
L = L - truck[i];
ans++;
}
else {
i--;
ans++;
continue;
}
}
while (success.size() != n) {
func1();
ans++;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> w >> L;
for (int i = 1; i <= n; i++) {
int num;
cin >> num;
truck[i] = num;
}
func();
cout << ans << '\n';
return 0;
}