[백준 BOJ] 1940번 주몽 (C++/cpp)

문제 설명

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

1940번: 주몽

 

접근 방법 - 두 포인터 알고리즘의 기초 문제

백준의 1940번 문제는 두 포인터를 이용하여 간단하게 해결할 수 있는 문제이다.

해당 문제는, 재료로 주어지는 고유 번호들 중 2개를 적절히 조합하여 갑옷을 만들 수 있을 때 만들 수 있는 갑옷의 개수를 구하여 출력해야 하는 문제이다.

이때 두 포인터는, 진짜로 포인터의 개념을 이용해야 하는 것이 아닌, 2개 이상의 변수를 배열/벡터의 인덱스로 사용하는 원리를 이용한 알고리즘을 뜻한다.

필자와 같은 경우에는, 특정 숫자를 만들어내는 데에 2개의 숫자를 사용해야 한다는 점에서 착안하여, 숫자들을 정렬한 뒤 작은 숫자 - 큰 숫자의 크기를 각각 적절히 조절해 가며 한 쌍씩 만들어내도록 하였다.

자세한 설명은 아래 마저 작성하니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 코드와 설명을 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 입력값으로 주어지는 재료들의 고유 숫자를 저장할 배열(arr)을 전역 변수로 선언해 둔다.

 

2) 재료의 개수(n)와 갑옷 제작에 필요한 번호(m)를 순차적으로 입력받는다.

뒤이어 n의 크기만큼, arr의 값들을 하나씩 입력받는다.

 

3) sort() 함수를 사용하여, arr의 값들을 오름차순 정렬한다.

 

4) 두 포인터 알고리즘으로, arr의 값을 가리킬 포인터 변수 start와 end 변수를 각각 선언한다.

그리고, start는 arr의 가장 작은 값을 가리키도록 0으로 초기화한다.

end의 경우엔 arr의 가장 큰 값을 가리키도록 n-1로 초기화한다.

 

5) 만들 수 있는 갑옷의 수를 저장할 변수 cnt를 0으로 초기화하여 선언한다.

 

6) 무한 반복문을 통해, 아래의 연산을 반복하며 취한다.

(이때 반복문의 조건은, start의 값이 end의 값을 역전하지 않도록 설정해 둔다.)

- sum 변수를 선언하고, start와 end가 각각 가리키는 arr의 2개 값을 더한 결괏값을 저장하도록 한다.

- sum의 값이 m과 동일하다면, 이는 해당 값으로 갑옷을 만들 수 있다는 것을 뜻한다. 따라서 이 경우엔, cnt에 1을 더한 뒤에 end에 1을 빼서 다른 조합을 찾도록 연산한다. (start에 1을 더해도 상관없다.)

- sum의 값이 m보다 크다면, sum의 값을 줄여서 갑옷을 만들게끔 해야 한다. 따라서, end 값을 1 줄여서 현재보다 다소 작은 값을 더하게끔 한다.

- sum의 값이 m보다 작다면, sum의 값을 키워서 갑옷을 만들게끔 해야 한다. 따라서, start 값을 1 늘려서 현재보다 다소 큰 값을 더하게끔 한다.

 

7) 6)의 연산이 모두 완료되었다면, 최종적으로 저장된 cnt의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 1940번 코드
int arr[15001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);

	int start = 0;
	int end = n - 1;
	int cnt = 0;
	while (end - start > 0) {
		int sum = arr[start] + arr[end];
		if (sum == m) {
			cnt++;	end--;
		}
		else if (sum > m) { end--; }
		else { start++; }
	}
	cout << cnt << endl;
}

 

제출 결과

(2022.10.03 백준 1940번 문제 제출 결과)