11/19 좋은 수

삼성 코드그라운드에서 제공하는 알고리즘에 관한 개인적인 풀이를 정리했습니다.

아래 사이트에서 직접 풀어보실 수 있습니다.

 

https://www.codeground.org/practice

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

 

처음 이 문제를 봤을 때는 배열을 순회하면서 현재 수 보다 앞에 있는 수들을 재귀 호출을 통해 더해보면서 좋은 수를 판별하는 방식을 생각했다.

#include <iostream>
#include <cstring> 
using namespace std;

int Answer, arr[5000], chk[200000]; //좋은 수(첫 코드, 시간 초과)

void getGoodNum(int objIdx, int prev, int idx, int sum) {
	if (chk[objIdx]) return;
	if (idx == 3) {
		if (sum == arr[objIdx]) {
			Answer++;
			chk[objIdx] = 1;
		}
		return;
	}
	for (int i = prev; i < objIdx; i++) {
		getGoodNum(objIdx, i, idx+1, sum + arr[i]);
	}
}

int main(int argc, char** argv)
{
	int T, test_case;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		memset(chk, 0, sizeof(chk));
		Answer = 0;
		int i, n;
		cin >> n;
		for (i = 0; i < n; i++) {
			cin >> arr[i];
		}

		for (i = 1; i < n; i++) {
			getGoodNum(i, 0, 0, 0);
		}
		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;
}

처음 생각한 코드. 시간 초과가 발생할 뿐만 아니라 음수 입력이 들어오면

chk 배열에 들어가지 못해 프로그램이 죽어버린다.

 

 

처음 생각한 대로 코드를 적당히 짜보고 실행해보니 테스트 케이스는 통과했지만, N이 더 크게 늘어났을 때는 시간제한에 걸리는 것을 확인할 수 있었다. 이는 시간 복잡도가 O(N^3)인 getGoodNum 메소드를 n-1번 실행하여 전체 코드의 총 시간복잡도가 O(N^4)가 되기 때문이었다. 나는 이 방법으로는 풀 수 없다는 것을 느끼고 다른 방법을 찾아야 했다.

 

 

 

 

특별한 방법이 생각나지 않아 구글링을 해보던 중, 세 가지 수가 아닌 두 수의 합만 배열에 저장해놓으면 O(N^2)의 시간복잡도로 문제를 풀 수 있다는 것을 알게 되었다. i번째 수를 좋은 수인지 판별하기 위해서 0번째 수부터 i-1번째 수에서 2개의 수를 뽑아 더한 값이 i번째 수 - (0번째 수 ~ i-1번째 수)인지를 확인하고 같은 값이 있다면 i번째 수를 좋은 수라고 판별하는 방식으로 i를 0부터 n까지 돌리면 문제를 O(N^2) 시간 안에 풀 수 있다.

 

 

전체 코드는 다음과 같다.

#include <iostream>
#include <cstring>
using namespace std;

int Answer, arr[5000], chk[400001]; //좋은 수

int main(int argc, char** argv)
{
	int T, test_case;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		Answer = 0;
		int i, j, n;
		cin >> n;
		for (i = 0; i < n; i++) {
			cin >> arr[i];
		}
		memset(chk, 0, sizeof(chk));
		for (i = 0; i < n; i++) {
			for (j = 0; j < i; j++) { // 두 수의 합을 저장하는 배열을 채운다.
				if (!chk[arr[i-1] + arr[j]+200000]) chk[arr[i-1] + arr[j] + 200000] = 1;
			}

			for (j = 0; j < i; j++) {
				if (chk[arr[i] - arr[j] + 200000]) {
					Answer++;
					break;
				}
			}
		}
		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;
}