[C++] 백준 1940번 주몽

 

피곤하다...

 

 

문제

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

1940번: 주몽

 

 

이 문제는 예전에 풀었던 투포인터를 사용한 문제랑 비슷한 것 같다. 그래서 일단 오름차순으로 정렬한 후에 양쪽 끝에서부터 더해가며 확인하면 될 것 같다.

 

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

int n, m, a;
int A[15001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	sort(A, A + n);

	int start=0, end=n-1, count=0, sum;


	while (start < end) {
		sum = A[start] + A[end];
		if (sum == m) {
			count++;
			start++;
			end--;
		}
		else if (sum < m) {
			start++;
		}
		else {
			end--;
		}
	}

	cout << count << "\n";
	
	return 0;
}

 

그래서 정렬을 한 후에 양쪽 끝에서부터 시작하여 수를 더했을 때 m이 되는지 비교하였고, 만약 m이 되면 count를 해준 후 각 포인터를 다음에 비교할 부분으로 하나씩 옮겨주었다. m보다 작으면 수가 더 커져야 한다는 뜻이니까 앞에 있는 포인터인 start를 하나 뒤로 옮겨주고 m보다 크면 수가 작아져야 한다는 뜻이니까  뒤에 있는 포인터인 end를 하나 앞으로 옮겼다.

 

 

 

 

 

 

다른 풀이를 찾아보니 이 분은 포인터 하나의 값이 끝까지 가면 시작점 하나 올리고 다시 반복하도록 하였다. 즉, 포인터 2개가 같은 방향으로 이동한다는 것 같다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,M;
vector<int> v;

int main() {
    cin >> N >> M;

    for(int i=0;i<N;i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }

    int start=0, end=1, cnt=0;
    sort(v.begin(),v.end());

    while(start<=end && end<N) {
        if(v[start] + v[end] == M) cnt++;

        if(end==N-1) {
            start++;
            end=start+1;
        } else end++;
    }

    cout << cnt;
}
출처: https://tooo1.tistory.com/274 [개발자 퉁이리:티스토리]

 

 

 

또 다른 분은 이중 for문을 사용하여 해결한 것을 볼 수 있었다.

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

int N, M;
int arr[10000001];
int cnt = 0;

int main(){
  scanf("%d", &N);
  scanf("%d", &M);

  for(int i = 0; i < N; i++){
    scanf("%d", &arr[i]);
  }

  sort(arr, arr + N); // array sort

  // 갑옷은 고유 번호 가지고 있어서 2 pointer 가능
  for(int i = 0; i < N; i++){
    for(int j = N-1; j > i; j--){
      if(arr[i] + arr[j] == M){
        i++;
        cnt++;
      }
    }
  }

  printf("%d", cnt);

  return 0;
}
출처: https://velog.io/@lamknh/C-%EB%B0%B1%EC%A4%80-1940-%EC%A3%BC%EB%AA%BD

 

 

 

 

이렇게 풀다 보니까 같은 문제라도 정말 다양한 풀이 방법이 나오는 것 같다.

나중에는 내가 효율적인 방법의 알고리즘을 뚝딱 작성할 수 있게 되면 좋겠다.