[백준/C++] 2010 플러그

문제 링크

https://www.acmicpc.net/problem/2010

2010번: 플러그

 

문제

선영이의 집에는 콘센트를 꽂을 수 있는 플러그가 하나밖에 없다. 선영이는 많은 컴퓨터를 가지고 있는데, 컴퓨터의 전원 문제는 어떻게 해결하는 것일까?

하나의 플러그가 있고, N개의 멀티탭이 있다. 각 멀티탭은 몇 개의 플러그로 이루어져 있다고 한다. 최대 몇 대의 컴퓨터를 전원에 연결할 수 있을까?

입력

첫째 줄에 멀티탭의 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 이어서 둘째 줄부터 N개의 줄에 걸쳐 각 멀티탭이 몇 개의 플러그를 꽂을 수 있도록 되어 있는지를 나타내는 자연수가 주어진다. 이 자연수는 1,000을 넘지 않는다.

출력

첫째 줄에 최대로 전원에 연결될 수 있는 컴퓨터의 수를 출력한다.

예제 입력 1 복사

3
1
1
1

예제 출력 1 복사

1

예제 입력 2 복사

2
5
8

예제 출력 2 복사

12

---

문제 풀이

이 문제를 풀 때 가장 중요한 점은 플러그의 연결방법이다.

첫번째 예제처럼 멀티탭이 3개가 있는데, 각 멀티탭의 플러그가 1개씩밖에 없다면 첫번째 멀티탭 위에 두번째 멀티탭을 연결고, 그 위에 세번째 멀티탭을 연결해야 한다. 콘센트를 꽂을 수 있는 플러그가 벽에 있다면, 그 벽에 계속 돌출되는 그림을 상상하면 된다.

알고리즘을 짤 때 가장 직관적인 방법은 그림을 그려보는 것이므로 나는 노트에 그림을 그리며 이해해봤다.

아래 예시로 생각해보자.

멀티탭이 4개가 있고, 순서대로 4, 3, 2, 5개의 플러그를 꽂을 수 있다면 최대로 전원에 연결될 수 있는 컴퓨터의 수가 몇개있을까?

최대로 전원에 연결될 수 있는 컴퓨터의 수를 구해야 하니, 플러그의 사용을 최소화하며 멀티탭 4개를 순서대로 연결해야 한다. 즉, 멀티탭에 1개의 플러그만 남겨 그 플러그는 다음 멀티탭에 연결해야 한다. 그럼 아래와 같은 그림이 완성된다.

빨, 주, 노, 초 순서로 멀티탭을 연결했을 때를 그려보았다. 각 멀티탭을 연결하는 것은 그 전 멀티탭의 플러그 1개이므로, 각 멀티탭 사이에는 공통된 플러그가 있다. 이 부분을 이용하면 아주 쉽게 코드를 짤 수 있다. 처음에는 이 문제를 배열을 이용하여 풀어야하나 고민이 많았는데, 멀티탭 사이간의 공통된 플러그를 생각해보면 그냥 산수문제인 것을 알 수 있다.

결론적으로 답은

각 멀티탭의 플러그의 갯수의 합 - (멀티탭의 갯수-1)

이다. 간단하게 모든 플러그의 수를 더한 후, 공통된 플러그의 갯수를 빼주면 되기 때문이다.

개인적으로 이 문제가 인상깊었던 이유는, 처음 문제를 보았을 때 다양한 반복문과 함수를 써가며 복잡하게 생각했는데, 그림을 그려보니 아주 쉬운 식 하나만 세워 출력할 수 있었기 때문이다. 역시 알고리즘을 짤 때에는

1. 직접 써보며 문제에 접근하기

2. 더 간단한 방법이 없을까 고민하기

를 생각하면 도움이 많이 되는 것 같다. 복잡하게 다양한 함수를 써서 풀어야만 할 것 같은 알고리즘에 대한 나의 꽉 막힌 시야를 틔게 해준 문제다.

코드

#include <iostream>
using namespace std;

int N, A=0, cnt=0;
int p[500001];
int main(){
  cin >> N;
  for(int i=0; i<N; i++){
    cin >> p[i];
    A = A + p[i];
    cnt ++;
  }
  cout << A-(cnt-1);
}