늘

문제부터 보면 전형적인 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 = ..