[배열 | 기본문제] 3273번 : 두 수의 합

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

3273번: 두 수의 합

---

내 제출 코드

#include<bits/stdc++.h>
using namespace std;

int num[1000001];	// 수열에 해당 index 정수들이 존재하는지 확인하기 위한 배열
int x,n;	// 비교값, 수열 수

int main()
{
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	
	cin >> n;
	int a, sum = 0;
	int arr[100001];
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		arr[i] = a;
		num[a] = 1;
	}

	cin >> x;
	for (int i = 0; i < n; i++)
	{
		if (x - arr[i] < 0) continue;	//idx가 음수되면 패스(break아님;)
		if (num[x - arr[i]] == 1)
			sum++;
	}

	cout << sum/2;	//쌍이라서 중복 빼려고 나눠줌
}

수열의 크기가 100000이어서  시간 복잡도가 O(N²)이면 시간 초과가 나올거라고 생각.

=> 이중포문 구현 X

 

자꾸 런타임 에러(Out of Bounds)가 떠서 idx가 음수인지 검사하는 코드를 넣어주니 틀렸다고 나왔다.

아직 반례를 찾지 못했다.

( 찾아보니까 투포인터말고 배열로 푼사람들은 이런식으로 구현했던데 다 틀렷음,,)

 

당연히 알고리즘이 틀린게 없으니까 반례는 안나온다^^

break로 아예 탈출해버려서 틀렸다