백준 10773번 - 제로 (C/C++)

 

 

이전에 풀었던 문제와 제목이 비슷해보여서 친근해서 선택했다.

이번에도 0을 찾아내는 문제다.

 

 

 

 

입력
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)
이후 K개의 줄에 정수가 1개씩 주어진다. 
정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 
아닐 경우 해당 수를 쓴다.
정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력
재민이가 최종적으로 적어 낸 수의 합을 출력한다. 
최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

 

예를들어 4를 입력하면 총 4개의 숫자를 입력받게 되는데,

이때 원소에 0이 포함되어 있다면 그 앞 가장 최근의 원소를 지우거나 카운트되지 않도록 해야 한다.

(이때 그 앞의 원소도 0이라면 이 경우 원소를 패스하고 그 앞으로 넘어간다.)

 

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
using namespace std;


void calculate(vector<int>& vec, int i)
{
	if (vec[i] == 0)
	{
		if (vec[i - 1] != 0) { vec[i - 1] = 0; }
		else { calculate(vec, i - 1); }
	}

}

int main() {
	int K;
	cin >> K;

	vector<int> vec(K);
	for (int i = 0; i < K; i++) {cin >> vec[i];}

	for (int i = 1; i < K; i++) {calculate(vec, i);}
	
	int sum = accumulate(vec.begin(), vec.end(), 0);
	cout << sum << endl;
}

 

그 이전의 원소에 대한 함수를 호출하기 위해 calculate라는 함수를 따로 만들어주었다.

 

 

 

void calculate(vector<int>& vec, int i)
{
	if (vec[i] == 0)
	{
		if (vec[i - 1] != 0) { vec[i - 1] = 0; }
		else { calculate(vec, i - 1); }
	}

}

calculate 함수는 for문 내에서 vector의 요소에 0이 포함되어있는지 확인하고,

가장 최근의 수를 지우는 알고리즘을 수행하는 함수로 사용했다.

 

만약 vec[i-1]의 원소가 0이라면, 다시 calculate( vec, i-1)의 함수를 순회한다. 이 과정을 반복한다.

 

int sum = accumulate(vec.begin(), vec.end(), 0);

 

accumulate()은 C++내에서 벡터 값들의 합산을 출력해준다.

사용 방법은 vec.begin(), vec.end()를 사용해 구간을 설정해준다는 점은 같고,

sum 변수의 시작 위치를 0으로 설정해주면 된다.