1940번 난이도:실버 4 (주몽의 명령)

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

1940번: 주몽

 

풀이과정 1

 

1. 일단 받을 재료의 수, 갑옷이 완성되는 번호의 합을 입력받는다. 그리고 재료들을 입력받는다.

 

2. 재료들을 정렬을 해주어야한다. 그 다음에 시작인덱스와 끝인덱스를 정해서 완성되는 번호의 합이 몇개가 나오는지 출력하면 된다.

 

3. 정렬은 알고리즘 헤더파일의 sort 정렬을 이용하자

 

4. 시작인덱스를 고정시키고, 끝 인덱스를 뒤에서부터 시작인덱스까지 이동시키며 두개의 합이 갑옷이 완성되는 합이 되는 지 판단한다. 그리고 시작인덱스를 한 칸 이동시키고 이 과정을 반복한다.

 

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

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin.tie(NULL);

	int num;// 받을 재료의 수
	cin >> num;
	int sum;// 완성되는 번호의 합
	cin >> sum;
	vector<int> A(num, 0);

	for (int i = 0;i < num;i++) {
		cin >> A[i];
	}

	sort(A.begin(), A.end());

	int count = 0;

	for (int i = 0;i < num;i++) {
		for (int j = num - 1;j > i;j--) {
			if(A[i]+A[j]==sum){
				count++;
			}
		}
	}
	cout << count;
}

 

for문을 사용하면 이렇게 풀 수 있고, while문을 사용하면 밑의 처럼 풀 수 있다.

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

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin.tie(NULL);

	int num;// 받을 재료의 수
	cin >> num;
	int sum;// 완성되는 번호의 합
	cin >> sum;
	vector<int> A(num, 0);

	for (int i = 0;i < num;i++) {
		cin >> A[i];
	}

	sort(A.begin(), A.end());

	int count = 0;
	int i = 0;
	int j = num - 1;
	while(i<j){
		if (A[i] + A[j] < sum) {
			i++;
		}
		else if (A[i] + A[j] > sum) {
			j--;
		}
		else {
			count++;
			i++;
			j--;
		}

	}
	cout << count;
}