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

- 문제 (17952번) : 과제는 끝나지 않아!

• 링크 : https://www.acmicpc.net/problem/17952

• 이번 학기에 받을 과제 점수 구하는 문제.

  • 과제 해결규칙
    1. 과제는 가장 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다.
    2. 과제를 하던 도중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행
    3. 새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다.
       ( 내가 하던 부분을 기억할 수 있음. )

---

- 입력 및 출력

[ 입력 ]

• 첫번째 줄에 이번 학기가 몇 분인지 N 입력
• 두번째 줄부터 N줄동안 학기가 시작하고 N분째에 주어진 과제의 정보가 주어짐.
  • 1 A T : 과제의 만점 A, 과제를 해결하는데 T시간 소요
  • 0 : 해당 시점에 과제가 주어지지 않음.

• 1 ≤ N ≤ 1,000,000 || 1 ≤ A ≤ 100 || 1 ≤ T ≤ 1,000,000

[ 출력 ]

• 이번 학기에 받을 과제 점수 출력

---

- 문제 풀이

• 학기 중 나오는 과제를 해결 할 때 규칙을 보면

  • 가장 최근에 나온 순서대로 한다.
  • 과제를 하던 도중 새로운 과제가 나온다면 중단 후 새로운 과제부터 해결한다.

  이 두가지 조건을 봤을 때 stack으로 해결하면 된다는 것을 알 수 있다.
  ( ∵ stack은 최신 것을 먼저 해결함. )
  

• 나는 점수를 저장하는 stack과 소요시간을 계산하는 stack을 따로 나눠 생각했다.
  ( 어차피 점수와 소요시간은 쌍으로 입력받기 때문에 순서가 흐트러지지 않는다. )

• 과제가 나온다면, 즉 1을 입력받으면 추가적으로 점수와 소요시간을 입력받아 각각의 stack에 저장해준다.

• 그 후 과제는 받으면 바로 해결한다고 했으므로 0이든 1이든 상관없이 남은 시간 - 1 계산을 해준다. ( 이 때 소요시간 계산하는 stack이 비어있지 않을 경우만 행해야한다. )

• -1 계산 후 소요시간이 0이라면 과제를 해결한 것이므로 현재 점수를 저장하는 stack의 top element를 결괏값에 더해주고, 소요시간과 점수를 pop해준다.

• 최종적으로 더해준 결괏값을 출력해준다.

• 이 문제에서의 핵심은 가장 최근에 들어온 과제부터 해결 하는 것이다.
  => stack으로 해결
  => 이 때 하나의 stack을 사용해서 쌍으로 stack에 저장해도 되고, 점수와 소요시간을 각각 하나의 stack을 사용해 계산해도 된다.

---

- 최종 코드