문제
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
출력
문제의 조건을 만족하는 쌍의 개수를 출력한다.
풀이
풀이 1
#include <bits/stdc++.h>
using namespace std;
const int SIZE=10;
int main (void){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> sequence;
while(n--){
int t;
cin >> t;
sequence.push_back(t);
}
int targetNum;
cin >>targetNum;
int result=0;
for(int i=0; i<n-1; i++){ //5 12 7 10 9 1 2 3 11
for(int j=i+1; j<n; j++){
if(sequence[i]+sequence[j] == targetNum){
result++;
cout << sequence[i]<<", "<<sequence[j]<<"\n";
}
}
}
cout << result;
return 0;
}
풀이 2
모든 값의 등장여부를 저장하는 배열을 하나 만들고 값이 이전에 등장했는지 여부를 확인하는 방식의 풀이
풀이 1은 어떻게 하든간에 시간 복잡도 O(n^2)을 벗어나지 못한다.
때문에 배열의 저장공간을 이용하여 모든 값 (주어진 수의 범위)의 등장 여부를 저장하는 배열 occur를 하나 만들어서 ai+aj = x를 만족하는 쌍이 있는지 확인할 수 있다.
#include <bits/stdc++.h>
using namespace std;
const int SIZE=1000001;
int main (void){
ios::sync_with_stdio(0);
cin.tie(0);
int occurs[SIZE] = {0,};
int n;
cin >>n;
vector <int> numbers; //5 12 7 10 9 1 2 3 11
//수열에 포함되는 수 입력받기
for(int i=0; i<n; i++){
int t;
cin >>t;
occurs[t]++;
numbers.push_back(t);
}
int x;
cin >>x;
int answer=0;
for(int i=0; i<n; i++){
if(x-numbers[i]>0 && occurs[x-numbers[i]]){ //occurs[13-5] == occurs[8]이 존재하면 answer ++;
answer++;
}
}
cout << answer/2;
return 0;
}틀렸다... 자꾸 out of bounds 런타임에러가 뜬다.
풀이 3
#include <bits/stdc++.h>
using namespace std;
const int SIZE=2000001;
int main (void){
ios::sync_with_stdio(0);
cin.tie(0);
int occurs[SIZE] = {0,};
int n, t, x, answer=0;
cin >>n;
vector <int> numbers; //5 12 7 10 9 1 2 3 11
//수열에 포함되는 수 입력받기
for(int i=0; i<n; i++){
cin >>t;
occurs[t]++;
numbers.push_back(t);//5 12 7 10 9 1 2 3 11
}
cin >>x;
for(int i=0; i<n; i++){
//5 12 7 10 9 1 2 3 11
if(x-numbers[i]>0 && occurs[x-numbers[i]]){ //occurs[13-5] == occurs[8]이 존재하면 answer ++;
answer++;
}
}
cout << answer/2;
return 0;
}이 부분에서
occurs[x-numbers[i]]
풀이 1,2는 occurs 범위가 1000001이었다. 그런데 x-numbers[i]가 2000001범위내에 있어서 out of bound 오류가 난 것이었다. 때문에 occurs 범위를 2000001로 변경하니 맞았다!
풀이 - 출처
https://github.com/sudaltokki/Algorithm/tree/main/%EB%B0%B1%EC%A4%80
#include <bits/stdc++.h>
using namespace std;
int n, a[100000], x, tmp[2000001], num = 0;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cin >> x;
for (int i = 0; i < n; i++) {
tmp[a[i]]++;
if (x - a[i] > 0 && tmp[x - a[i]] == 1) num++;
}
cout << num;
}친구의 코드~
처음에
if (x - a[i] > 0 && tmp[x - a[i]] == 1) num++;
tmp[a[i]]++;-
이렇게 하면 틀린다
왜???
만약 x=12이고 n=6이 들어오게되면 tmp[6] = 1이 되고
그 다음줄에서 6이 존재한다고 읽어버리기 때문에 틀리게 된다. -
그리고!! && 연산자를 쓸 때 앞의 조건에서 false가 뜨면 && 뒤의 조건들은 실행되지 않고 false 처리가 된다.
이렇게 두개 !
좋은 문제였다....
스터디에서 나온 결로은 이런 반례를 찾기 어렵기 때문에 아예 풀이2처럼 입력과 숫자 등장 여부를 따로 분리해서 출력하는 것이 좋다.
