[백준(BOJ)] 17952번 과제는 끝나지 않아! C++

문제 : https://www.acmicpc.net/problem/17952

17952번: 과제는 끝나지 않아!

 

어떤 문제인가?

참 공감되는 문제다ㅎㅎ

입력받은 N분동 안 해결한 과제의 총점을 출력하는 문제이다.

기존 과제를 끝내지 않고 새로 받은 과제부터 끝내는 로직이 존재한다.

 

실제로 저렇게 하면 효율이 많이 떨어질 텐데ㅎㅎ.. 하지만 문제니까^^

 

 

 

접근 방법

1이 입력됐을 때는 가장 최근의 과제를 해야 한다.

처음엔 stack을 사용해보려고 했는데 stack에 과제 해결 점수와 남은 시간을 모두 저장하기가 번거롭다고 느꼈다.

 

그래서 vector와 pair를 통해 과제 해결 점수와 남은 시간을 저장하기로 했다.

vector<pair<int, int>> homework;

 

 

 

int n;
char order;
int total = 0;

cin >> n;

for (int i = 0; i < n; i++) {
    cin >> order;

문제의 조건대로 입력을 받는다.

그리고 for문을 반복하며 1, 0 일 때에 관한 연산을 수행한다.

 

if (order == '1') {
    int a, b;
    cin >> a >> b;

    if (b - 1 == 0) {
        total += a;
    } else {
        homework.push_back(pair<int, int>(a, b - 1));
    }
} 

먼저 1일 때다.

이때는 새로운 과제가 주어지므로 따로 입력을 받는다.

 

그리고 이때 b가 1이라면 별도에 작업 없이 바로 total에 추가해준다.

그 이유는 그 과제가 입력된 시점부터 1분째이므로 바로 과제가 끝나기 때문이다.

 

해결 시간이 1보다 크다면 vector에 과제 해결 점수와 해결 시간 - 1을  추가한다.

여기서도 위와 같은 이유로 입력된 시점부터 1분이 지나기 때문이다.

 

 else {
    if(!homework.empty()){
        homework.back().second--;
    }

    if (!homework.empty() && homework.back().second <= 0) {
        total += homework.back().first;
        homework.erase(homework.end() - 1);
    }
}

그다음으로 0이 입력됐을 때다.

 

이때는 새로 주어진 과제가 없으므로 기존에 있던 과제를 수행하면 된다.

따라서 vector가 비어있지 않다면 vector의 back의 second를 1 감소시켜준다.

 

다음으로 vector가 비어있지 않다고 vector의 back의 second가 0 이하라면

total에 vector의 back의 fisrt(과제 해결 점수)를 추가한다.

그리고 그 원소를 지워버린다.

 

그럼 이제 가장 최근의 과제부터 다시 시작하는 것이다.

 

 

cout << total;

반복문을 마친 후 total을 출력해주면 끝!

 

 

무엇이 어려웠는가?

문제를 읽으며 바로 머리에 어떻게 해야 할지 떠올라서 어렵게 느껴지지 않았다.

 

 

 

시간 복잡도

먼저 입력받은 n번만큼 for문을 반복한다.

for문 안에 있는 연산들은 모두 O(1)의 시간 복잡도를 갖는다.

따라서 전체 시간 복잡도에 영향을 주지 않으므로 시간 복잡도는 O(n)이 된다.