BOJ 2010 - 플러그

문제

BOJ 2010 - 플러그

하나의 콘센트에 N개의 멀티탭을 이어서 꽂을 때, 사용 가능한 최대 플러그 수를 구하라. 멀티탭을 연결하면 구멍 하나를 사용한다.

입력

첫째 줄에 멀티탭 수 N, 이후 N줄에 각 멀티탭의 구멍 수가 주어진다.

출력

사용 가능한 최대 플러그 수를 출력한다.

예제

풀이

첫 번째 멀티탭을 제외하고 나머지는 이전 멀티탭의 구멍 하나를 사용하므로, 전체 구멍 합에서 (N-1)을 빼면 된다.

1. 각 멀티탭의 구멍 수에서 1을 뺀 값을 누적한다 (연결에 사용되는 구멍)
2. 마지막에 1을 더한다 (마지막 멀티탭은 연결할 필요 없음)
3. 결과를 출력한다

핵심 아이디어: N개의 멀티탭을 직렬 연결하면 N-1개의 구멍이 연결에 사용되므로, 총 구멍 수 - (N-1)이 답이다.

코드

#include <iostream>
using namespace std;
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  int N = 0;
  cin >> N;
 
  int Input = 0, Sum = 0;
  for (int i = 0; i < N; ++i)
  {
    cin >> Input;
    Sum += Input - 1;
  }
 
  cout << ++Sum;
 
  return 0;
}

복잡도

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