BOJ 2506 - 점수계산

문제

N개의 문제 채점 결과가 주어진다. 맞히면 1점이고, 연속으로 맞히면 보너스가 1씩 누적된다. 틀리면 보너스가 초기화된다. 총점을 구하라.

입력

첫째 줄에 문제 수 N, 둘째 줄에 채점 결과(0 또는 1)가 공백으로 주어진다.

출력

총점을 출력한다.

예제

입력	출력
`10` `1 1 0 1 1 1 0 0 1 1`	`13`

풀이

순회하며 연속 정답 보너스를 관리하여 점수를 누적한다.

정답이면 기본 1점을 더한다
이전 문제도 정답이었으면 보너스를 1 증가시키고 보너스만큼 추가 점수를 더한다
이전이 오답이었으면 보너스를 0으로 초기화한다
오답이면 점수를 더하지 않는다

핵심 아이디어: 연속 정답 시 i번째 연속이면 i점을 받으므로, 보너스 카운터 하나로 O(N)에 총점을 계산할 수 있다.

코드

#include <iostream>
using namespace std;
 
int main()
{
  int n, score = 0, res[100], bonus = 0;
  cin >> n;
 
  for (int i = 1; i < n + 1; i++)
  {
    cin >> res[i];
    if (res[i] == 1)
    {
      score++;
      if (res[i - 1] == 1)
      {
        bonus++;
        score += bonus;
      }
      else
      {
        bonus = 0;
      }
    }
  }
  cout << score;
 
  return 0;
}

복잡도

시간: O(N)
공간: O(N)

문제