[알고리즘/문제] 백준 1940번: 주몽 (C++)

#include <iostream>
#include <vector>

using namespace std;

int N, M, temp, cnt;
vector<int> vec;

int main() {
	cin >> N;
	cin >> M;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		vec.push_back(temp);
	}

	for (int i = 0; i < N-1; i++) {
		for (int j = i + 1; j < N; j++) {
			if (vec[i] + vec[j] == M) cnt++;
		}
	}

	cout << cnt;

	return 0;
}

 

N개의 수를 받아 두개를 더했을 때 M이 되는 경우의 수를 세면 되는 문제이다.

그냥 별 생각없이 for문 두개 순회하면서 비교했더니 정답이었다..

근데 시간이 넉넉해서 정답이었지 시간이 좀 더 부족하면 다른 방법을 써야할 거 같은데 다른 방법이 딱히 안떠오른다.

방법은 많이 있을거같은데..

 

뒤늦게 생각해보니 내가 조합을 구현한거였다. n개중에 2개를 뽑은거다.

삼중까지는 for로 조합을 구현해도 무리가 없으나 4개 이상 뽑아야하면 재귀함수로 구현을 해야함을 잊지말자.

 

정답코드도 같은 로직으로 되었다.

그런데 if로 m이 20만보다 큰 경우에는 0을 출력하도록 되어있었다.

if(m>200000) cout << 0 << '\n';
else{
~~~
}

시간 제한이 빡쎈 문제는 아예 안되는 경우를 if로 빼낸 것이라고 한다.

예외처리가 가능한 부분은 if를 통해 미리 처리하는 것이 또 하나의 꿀팁!

 

 

[조합 관련 게시글]

https://music-tech.tistory.com/47

[알고리즘/C++] 조합

https://music-tech.tistory.com/48

[알고리즘/C++] 재귀함수로 조합 구현하기

 

[인프런 강의]

https://inf.run/QKBXL

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 강의 - 인프런