오늘도 도서관에 왔다.
그런데 점심 먹고 이것저것 하다 보니 벌써 1시 45분이다 ㅎㅎ.
얼른 문제를 풀어야지...
문제
https://www.acmicpc.net/problem/3273
3273번: 두 수의 합
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
www.acmicpc.net
오늘의 문제이다.
음... 이 문제는 배열에 입력을 받고 그 배열을 오름차순으로 정렬해 주어야겠다.
그리고 앞이랑 뒤에 포인터로 가리켜서 비교해 보면 될 것 같다는 생각이 들어 이런 코드가 있나 찾아보니
https://ansohxxn.github.io/algorithm/twopointer/
이렇게 투 포인터 알고리즘이라는 것이 있었다.
투 포인터 기법이란, 두 개의 포인터를 만들어서 각각이 가리키는 원소에 의미를 부여하여 요구하는 문제를 해결하는 알고리즘이라고 한다.
이 문제에서는 포인터 두 개가 양끝에서 반대로 진행하는 것을 사용하면 될 것 같다.
왼쪽의 포인터는 오른쪽 포인터가 가리키는 수와 합쳤을 때 13이 되거나 오른쪽 포인터가 왼쪽 포인터와 부딪쳤을 때 오른쪽으로 한 칸 움직여준다.
오른쪽의 포인터는 왼쪽 포인터가 가리키는 수와 합쳤을 때 13이 아니거나 왼쪽 포인터와 부딪치지 않았을 때 왼쪽으로 한 칸 움직여준다.
그럼 코드를 작성해 보자~
...
//시간 초과된 코드
#include <iostream>
#include <algorithm>
using namespace std;
int a[100000];
int main() {
int n, x;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cin >> x;
sort(a, a + n);
int start = 0;
int end = n - 1;
int sum, result = 0;
while (start != n - 2) {
sum = a[start] + a[end];
if (sum == x) {
result++;
start++;
}
else {
end--;
}
if (start >= end) {
start++;
end = n - 1;
}
}
cout << result << "\n";
return 0;
}
...
... 그럼 그렇지
예제 입력으로 실행해 봤는데 알맞게 출력되어서 한 번에 맞출 것이라는 기대를 해버렸다...
혹시나 어제 배운 것처럼 main 시작 부분에 ios::sync_with_stdio(false); cin.tie(0); 를 쓰거나 cin, cout 대신 scanf, printf를 써보기도 했는데 결과는...
처참...
왜죠...??ㅠㅠ
도저히 모르겠어서 다른 풀이를 찾아보기로 했다...
오...??
#include <iostream>
#include <algorithm>
using namespace std;
int a[100000];
int main() {
int n, x;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &x);
sort(a, a + n);
int start = 0;
int end = n - 1;
int sum, result = 0;
while (start < end) {
sum = a[start] + a[end];
if (sum == x) {
result++;
start++;
end--;
}
else if(sum > x){
end--;
}
else {
start++;
}
}
printf("%d", result);
return 0;
}
뭐지???
이 분은 다른 언어이기는 한데 초반에는 나랑 비슷하게 푸셔서 while문 부분을 따라서 내 코드를 수정하니까 맞았다...??
sum 값이 x보다 크면 수가 작아져야 하기 때문에 end--
sum 값이 x보다 작다면 수가 커져야 하기 때문에 start++
sum 값과 x 값이 같으면 해당 수들은 다른 수들과 다시 비교할 필요가 없기 때문에 end--, start++, result++
아!!! 맞네... 내가 문제를 잘못 풀었네 ㅎㅎ.
#include <iostream>
#include <algorithm>
using namespace std;
int a[100000];
int main() {
int n, x;
cin>>n;
for (int i = 0; i < n; i++) {
cin>>a[i];
}
cin>>x;
sort(a, a + n);
int start = 0;
int end = n - 1;
int sum, result = 0;
while (start < end) {
sum = a[start] + a[end];
if (sum == x) {
result++;
start++;
end--;
}
else if(sum > x){
end--;
}
else {
start++;
}
}
cout<<result<<"\n";
return 0;
}
물론 cin, cout으로 써도 시간초과는 나지 않는다. 괜히 이상한 곳만 고치고 있었다 ㅎㅎ.
그리고 정렬 후 투포인터를 이용하는 법이 아닌 다른 방법으로 푸는 방법이 있다고 한다.
원소 체크를 해서 배열의 원소 a에 대해서 x-a가 배열에 있는지 체크하는 방법이라고 하는데...
#include <iostream>
using namespace std;
int num[100001];
int cnt[2000001];
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,tmp,x;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> tmp;
num[i]=tmp;
cnt[tmp] = 1;
}
cin >> x;
int sum = 0;
for (int i = 0; i < n; i++) {
// x-num[i]가 음수면 런타임에러나므로 조심
if (x-num[i]>=0 && cnt[x - num[i]] != 0 && x-num[i]>num[i]) {//i<j조건도 넣어준다.
sum += 1;
}
}
cout << sum;
return 0;
}
출처: https://haerang94.tistory.com/443
아.... 아...? 아!! 알겠다. 무슨 소리인지 모르겠어서 한참 쳐다봤네..ㅎㅎ
그니까 num [i]와 합쳤을 때 x가 되는 수가 있는지 알아보기 위해
x-num [i]이 0 이상이고, 입력을 받은 적이 있고, 중복으로 count가 되지 않아야 하니까 해당 num[i] 보다는 커야 하는 조건이 들어간 것이다.
오호 이렇게도 풀 수 있구나...
다음번에는 풀이를 잘 생각해야겠다.
'백준 > C++' 카테고리의 다른 글
[C++] 백준 10815번 숫자 카드 (6) | 2023.12.08 |
---|---|
[C++] 백준 10814번 나이순 정렬 (4) | 2023.12.07 |
[C++] 백준 2751번 수 정렬하기 2 (2) | 2023.12.05 |
[C++] 백준 2217번 로프 (2) | 2023.12.04 |
[C++] 백준 1764번 듣보잡 (2) | 2023.12.03 |