[백준/C++] 28419번: 더하기

문제

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

---

문제 요약

길이가 N인 수열이 주어졌을 때, 인접한 세 값을 1씩 증가시키는 연산을 원하는 만큼 반복할 수 있다.

 

연산을 최소한으로 사용하여 수열의 홀수 번째 위치에 있는 값들의 합과 짝수 번째 위치에 있는 값들의 합이 같아지도록 만들어야 한다.

 

최소 연산 횟수를 출력한다.

---

코드

#include <iostream>
#include <vector>

#define ll long long

using namespace std;

ll n, odd_sum, even_sum;
vector<int> v;


int main() {
	cin >> n;

	// 짝수 합, 홀수 합 계산
	for (int i = 1; i <= n; i++) {
		int num;
		cin >> num;
		if (i % 2 == 0) {
			even_sum += num;
		}
		else {
			odd_sum += num;
		}
	}

	// 예외 처리
	if (even_sum < odd_sum && n == 3) {
		cout << -1;
	}

	// 결과 출력
	else cout << abs(even_sum - odd_sum);

	return 0;
}

---

코드 설명

인접한 세 값을 1씩 증가시킨다는 것은 홀수 합과 짝수 합의 차이를 1 감소시키는 것과 같다.

 

즉, 연산을 1번 할 때마다, 차이를 1씩 감소시켜 결국 같게 만들 수 있다.

 

ex) 1 2 3 4 5 6 

초기: 홀수 합은 9, 짝수 합은 12, 차이는 3

 

=>  2 3 4 4 5 6 

초기: 홀수 합은 11, 짝수 합은 13, 차이는 2

 

=> 3 4 5 4 5 6 

초기: 홀수 합은 13, 짝수 합은 14, 차이는 1

 

=> 4 5 6 4 5 6 

초기: 홀수 합은 15, 짝수 합은 15, 차이는 0

---

1. 입력과 함께 짝수 합과 홀수 합을 구한다.

 

2. n이 3이고 짝수 합이 더 클 경우, 차이를 좁힐 수 없으므로 -1을 출력한다.

ex) 1 0 1

 

3. 다른 경우에는 차이(= 연산 횟수)를 출력한다.

---

고찰

처음에 파이썬으로는 '맞았습니다'를 받을 수 있었지만, C++로는 77%에서 '틀렸습니다'를 받았다.

 

원인은 '큰 수 연산' 때문이었다. 파이썬은 큰 수 연산 처리 자동으로 해주지만, C++에서는 long long 자료형을 사용해야 했다.

 

A는 최대 100,000까지 가능하고, N은 최대 100,000까지 가능하다.따라서, 홀수합/짝수합은 최대 100,000 × 50,000 = 5,000,000,000 이므로,int형의 범위인 -2,147,483,648 ~ 2,147,483,647를 벗어난다.

 

다음에는 문제를 푸는 방법을 생각해냈다면, 범위 계산과 시간 복잡도를 먼저 해보자.