백준 6884번 :: 소수 부분 수열

www.acmicpc.net/problem/6884

6884번: 소수 부분 수열

정말 오랜만에 알고리즘을 풀어본다. 

먼저 문제 자체는 간단하다. 테스트 수 t와 수열의 길이 n 을 입력받아 수열 내부에서 연속적인 인수들의 합이 소수가 되는지 검사하고 가장 짧은 연속 인수들을 찾아내는 것이다. 

 

가장 처음에는 수열의 길이를 받는 것을 보지 못해서 가변함수 등을 찾아봤다. 

아래는 입력 개수를 모를때 getc(stdin) 으로 입력을 모두 받은 후 공백으로 입력이 모두 끝났음을 확인해 while 문을 종료하는 코드이다. 또한 for 문에서는 반복자를 사용해 List의 값들을 출력해봤다. 

#include <iostream>
#include <list>
#include <iterator>

using namespace std;

int main() {
	int n;
	list<int> list;


	do {
		cin >> n;
		list.push_back(n);
	} while (getc(stdin) == ' ');

	for (auto iter = list.begin(); iter != list.end(); iter++) {
		cout << *iter << endl;

	}
}

 

다시 문제로 돌아와 수열의 길이가 주어지지만 수열의 길이가 원소들과 함께 주어지기 때문에 do while 문은 필요하다.  

 

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

int main() {
	int t, n;
	vector<int> v;
	
	cin >> t;

	for (int i = 0; i < t; i++) {
		do {
			cin >> n;
			v.push_back(n);
		} while (getchar() == ' ');


		for (int j = 2; j <= v[0]; j++) { // 소수 부분수열인지 검사하는 수열의 원소 수.. 2개, 3개.. 묶어서 합이 소수인지 검사
			for (int s = 1; s <= (v[0] + 1 - j); s++) { // 2개씩 묶어서 검사한다면 n-1 번 검사해야하고 3개씩 묶는다면 n-2번 검사
				int sum = 0;
				for (int k = s; k < s + j; k++) { //원소의 합을 계산
					sum += v[k];
				}

				bool IsPrime = true;
				for (int l = 2; (l ^ 2) < sum; l++) {
					if (sum % l == 0) {
						IsPrime = false;
						break;
					}
				}
				if (IsPrime) {
					cout << "Shortest primed subsequence is length " << j << ": ";
					for (int k = s; k < s + j; k++) {
						cout << v[k] << " ";
					}
					goto outside;
				}
			}
		}
		cout << "This sequence is anti-primed.";
	outside:
		cout << endl;
		v.clear();
	}
}

 먼저 list는 list[0] 으로 인덱스 접근하는게 제한되었다. 그래서 조금 익숙한 vector로 바꾸었고, 아래는 수열이 주어졌을 때, 존재하는 모든 합을 구하는 코드이다. 합을 구한 후에는 소수 판별을 하였고 l^2 < sum 으로 sum 을 l 로 계속해서 나누다가 l의 제곱이 sum보다 커지면 모두 확인해본것이므로 이렇게 사용하였다. 

 또한 다중 루프를 빠르게 빠져나오기위한 goto도 처음 사용해봤다. outside로 빠져나가 딱히 진행할 코드는 없었지만 뒤에 하나의 실행문이라도 필요했기 때문에 cout << endl;을 붙였다.

 하지만 이후에 t만큼 전체를 반복하기 위해 v 벡터의 원소를 모두 지우고 초기화할 필요가 있었다. 처음에는 v를 이중 벡터로 만들어서 첫번째 테스트를 v[0]에 저장, 두 번째를 v[1]에 저장하려했으나 초기화가 clear로 쉽게되어 굳이 그러지는 않았다. 

 

이대로 코드를 제출해봤지만 "시간 초과" 가 떴다. 자체적으로 실행해봤을 때, 문제에서는 숫자 뒤에 공백이 존재해서 그렇다고 생각했다. 

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
	int t, n;
	vector<int> v;
	string strInput; // 띄어쓰기 기준으로 N개의 수를 입력받을 String	
	string strNum = "";

	getline(cin, strInput);
	for (int i = 0; i < strInput.length(); i++)
	{
		if (strInput.at(i) == ' ')
		{
			t = atoi(strNum.c_str());
			strNum = "";
		}
		else
		{
			strNum += strInput.at(i);
			continue;
		}
	}
	t = atoi(strNum.c_str());

	for (int i = 0; i < t; i++) {

		// 숫자 입력 받기
		cin.ignore();
		getline(cin, strInput);

		strNum = ""; // 각각의 숫자를 저장할 임시 String
		for (int i = 0; i < strInput.length(); i++)
		{
			if (strInput.at(i) == ' ')
			{
				// 현재까지 저장한 문자(숫자)들을 Vector에 추가 후 String 초기화
				v.push_back(atoi(strNum.c_str()));
				strNum = "";
			}
			else
			{
				// 띄어쓰기가 나올 때까지 문자 더함
				strNum += strInput.at(i);
				continue;
			}
		}
		v.push_back(atoi(strNum.c_str()));


		for (int j = 2; j <= v[0]; j++) { // 소수 부분수열인지 검사하는 수열의 원소 수.. 2개, 3개.. 묶어서 합이 소수인지 검사
			for (int s = 1; s <= (v[0] + 1 - j); s++) { // 2개씩 묶어서 검사한다면 n-1 번 검사해야하고 3개씩 묶는다면 n-2번 검사
				int sum = 0;
				for (int k = s; k < s + j; k++) { //원소의 합을 계산
					sum += v[k];
				}

				bool IsPrime = true;
				if (sum >= 2) {
					for (int l = 2; (l ^ 2) < sum; l++) {
						if (sum % l == 0) {
							IsPrime = false;
							break;
						}
					}
				}
				else {
					IsPrime = false;
				}

				if (IsPrime) {
					cout << "Shortest primed subsequence is length " << j << ": ";
					for (int k = s; k < s + j; k++) {
						cout << v[k] << " ";
					}
					goto outside;
				}
			}
		}
		cout << "This sequence is anti-primed.";
	outside:
		cout << endl;
		v.clear();
	}
}

 

 따라서 위와 같이 숫자를 입력 받는 부분을 수정하였다. 보편적이게 getline으로 한줄 전체를 입력받아 공백을 기준으로 int로 변환해서 vector에 입력한다.  sum이 1 일 경우도 예외를 추가했다. 하지만 이러면 시간초과는 일어나지 않지만 틀렸습니다! 가 뜬다.

 

#include <iostream>
#include <vector>
#include <iterator>
#include <math.h>

using namespace std;

int main() {
	int t, n;
	vector<int> v;

	cin >> t;

	for (int i = 0; i < t; i++) {
		do {
			cin >> n;
			v.push_back(n);
		} while (getchar() == ' ');


		for (int j = 2; j <= v[0]; j++) { // 소수 부분수열인지 검사하는 수열의 원소 수.. 2개, 3개.. 묶어서 합이 소수인지 검사
			for (int s = 1; s <= (v[0] + 1 - j); s++) { // 2개씩 묶어서 검사한다면 n-1 번 검사해야하고 3개씩 묶는다면 n-2번 검사
				int sum = 0;
				for (int k = s; k < s + j; k++) { //원소의 합을 계산
					sum += v[k];
				}

				bool IsPrime = true;
				if (sum >= 2) {
					for (int l = 2; pow(l, 2) < sum; l++) {
						if (sum % l == 0) {
							IsPrime = false;
							break;
						}
					}
				}
				else {
					IsPrime = false;
				}

				if (IsPrime) {
					cout << "Shortest primed subsequence is length " << j << ": ";
					for (int k = s; k < s + j; k++) {
						cout << v[k] << " ";
					}
					goto outside;
				}
			}
		}
		cout << "This sequence is anti-primed.";
	outside:
		cout << endl;
		v.clear();
	}
}

    

백준에서 주는 입력값을 복사해보니 뒤에 공백이 입력되지 않았다. 그래서 다시 간단했던 이전 코드로 들어왔고, 
이전에 c++ 에서 제곱을 l^2 로 착각했는데 math.h 의 pow 함수를 사용해야한다는 것을 알았다.  

 

#include <iostream>
#include <vector>
#include <iterator>
#include <math.h>
#include <sstream>

using namespace std;

string intToString(int n)
{
	stringstream s;
	s << n;
	return s.str();
}

int main() {
	int t, n;
	vector<int> v;

	cin >> t;
	vector<string> str(t);
	string tempstr;

	for (int i = 0; i < t; i++) {
		do {
			cin >> n;
			v.push_back(n);
		} while (getchar() == ' ');


		for (int j = 2; j <= v[0]; j++) { // 소수 부분수열인지 검사하는 수열의 원소 수.. 2개, 3개.. 묶어서 합이 소수인지 검사
			for (int s = 1; s <= (v[0] + 1 - j); s++) { // 2개씩 묶어서 검사한다면 n-1 번 검사해야하고 3개씩 묶는다면 n-2번 검사
				int sum = 0;
				for (int k = s; k < s + j; k++) { //원소의 합을 계산
					sum += v[k];
				}

				bool IsPrime = true;
				if (sum >= 2) {
					for (int l = 2; pow(l, 2) <= sum; l++) {
						if (sum % l == 0) {
							IsPrime = false;
							break;
						}
					}
				}
				else {
					IsPrime = false;
				}

				if (IsPrime) {
					tempstr = "Shortest primed subsequence is length " + intToString(j) + ": ";
					for (int k = s; k < s + j; k++) {
						tempstr += intToString(v[k]) + " ";
					}
					goto outside;
				}
			}
		}
		tempstr = "This sequence is anti-primed.";
	outside:
		str[i] = tempstr;
		v.clear();
	}

	for (int i = 0; i < t; i++) {
		cout << str[i] << endl;
	}
}

이후 입력과 출력을 따로 해야하나 싶어 vector<string>을 따로 만들어서 입력을 한번에 해봤지만 백준에서 정답처리는 되지 않았다. to_string을 사용하려했지만 찾아보니 VC11 이전버전에서 오류가 발생한다고 했다. 

그래서 정수를 stringstream으로 보내고 str() 함수를 통해서 int를 string으로 변환시키는 방법을 선택했다. 

 

아래는 마지막 수정된 코드이며 정상적으로 작동하는 것을 볼 수 있다. 하지만 백준에서는 "시간 초과"가 뜨지만 해결하지 못했다. 

정말 오랜만에 푸는 알고리즘이라 그런지 시간도 오래 걸렸고 결국 해결하지도 못한 것 같다.