BOJ 13335 - 트럭 https://www.acmicpc.net/problem/13335
얼핏봐서는 어렵게 느껴질 수 있으나, 문제 내용을 자기가 이해하기 쉬운 표현으로 따로 정리하고 주어진 그림을 잘 보면서 코드를 짜면 쉬운 문제다.
처음에는 ‘그리디인가..?’ 라는 생각을 했는데, 그냥 평범하게 시뮬레이션 문제인 것 같다.
문제 내용을 이해하기 쉽게 정리하기
문제를 읽어보면 단위길이, 단위시간이라는 표현이 나온다.
큰 의미는 없지만 이해하기 쉽게 우리가 잘 아는 단위로 변경해보자.
다리의 길이는 w 단위길이이며, 각 트럭들은 하나의 단위시간에 하나의 단위길이만큼 이동할 수 있다고 가정한다.
-> 1미터짜리 트럭이 있고 w미터짜리 다리가 있는데, 이 트럭은 1초에 1미터씩 이동할 수 있다.
동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.
-> 두번째 줄이 읽는 사람을 헷갈리게 만들 수도 있는데, 그냥 다리에 들어오는 중과 다리에서 나가는 중이라는 상태를 머리에서 잠시 지워버리자. 들어오면 들어온거고 나가면 그냥 나간거다.
이제 필요한 것은 다리의 최대하중을 고려하면서 시뮬레이션을 하는 코드를 작성하는 것이다.
코드
나같은 경우는 아래와 같이 디자인 했다.
class Truck {
int weight; // 트럭 하중
int entryTime; // 트럭이 다리에 진입한 시각
}
Queue<Truck> bridge; // 다리에 올라간 트럭들을 담아두는 큐
int currWeight; // 현재 다리에 올라가있는 트럭의 하중 합계
int currTruck; // 이번에 다리에 진입해야할 트럭 번호
int time; // 현재까지 소요된 시간
현재 다리의 상태가 진입 가능한 상태인지 체크하면서 트럭을 하나씩 큐에 넣고, 이 때 진입 시각을 기록해둔다.
time을 1씩 늘려가면서 큐의 맨앞에 있는 트럭이 다리를 빠져 나올 시간이 됐는지 체크하고, 큐에서 제거한다.
이 작업을 마지막 트럭이 빠져나올 때까지 반복한 뒤 time을 출력해주면 된다.