늘

문제부터 보면 전형적인 DP 문제라고 생각이 든다. 하지만 문제에 시간초를 보면 2초나 주어진다. 그래서 이 문제를 DP로 풀어야만 하는가 의문이 들면서 접근을 했다. 우선 문제 풀이 생각으로는 시간 제한도 2초이고 입력 수도 1000인것을 감안해서 넉넉하기 때문에 1일부터 Ti 시간만큼 뛰어가면서 전부 더해보는 방식으로 했다. #include #include #include using namespace std; int n; int visited[1001]; vector works; int answer; int pays; void start(int x, int pre) { if (x == n) { answer = max(answer, pays); return; } if (x > n) { answer = ..

어렵지 않았던 문제였다. 주의할 점으로는 동일한 시간대일때 트럭이 먼저 빠지고, 새로운 트럭이 들어갈 수 있다는 것이었다. 처음에 두개를 나눠서, 빠지는 데에 1초 + 들어가는데 1초를 해서 어디서 오류가 발생했는지 찾느라 조금 걸렸던것 빼곤 괜찮았다 ^^ #include #include using namespace std; int currentWeight; vector carsInBridge; // 다리위에 있는 차들의 무게와 시간 int solution(int bridge_length, int weight, vector truck_weights) { int answer = 1; for (int i = 0; i < truck_weights.size(); i++) { if (!carsInBridge.em..

진짜 간단해보였는데, 돌릴때마다 새로운 반례들을 만나면서 생각보다 시간이 오래걸렸다.. 알고리즘은 덱 이라는 자료구조를 이용하여 앞에서와 뒤에서 빼는 방식을 사용해야했다. 그렇지 않고 v.erase(v.begin())으로 앞에서 지우면 시간초과가 나왔다. 그리고reverse할 때, 진짜로 reverse하면 안되고 reverse했을땐 뒤에서, 정방향일 땐, 앞에서 pop해주는 방식으로 해결했다. 주저리 주저리 설명보단 역시 코드로 보는게 빠를듯 하다. 반례를 여러번 고치다보니 조금 지저분하긴 하다.... #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); in..