[BaekJoon Bronze2] C++: 블랙잭

Solved.ac Class.2에 있는 "블랙잭" 문제에 대한 풀이 및 탐구에 대한 기록.

정답률: 49.003%

목   차

 

문제 분석

Input: 

• 카드의 개수 N(3 ≤ N ≤ 100)과 맞춰야할 숫자 M(10 ≤ M ≤ 300,000)
• 카드에 쓰여 있는 수 : 100,000을 넘지 않는 양의 정수

Output: 

• M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합

문제 풀이

초안

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

using namespace std;

int main() {
	int cardCount, targetNum;
	vector<int> cardVec;
	int result = 0;

	cin >> cardCount >> targetNum;
	for (int i = 0; i < cardCount; i++) {
		int input;
		cin >> input;
		cardVec.push_back(input);
	}

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

	for (int i = cardCount - 1; i > 1; i--) {
		if (cardVec[i] >= targetNum) continue;
		for (int j = i - 1; j > 0; j--) {
			if (cardVec[i] + cardVec[j] >= targetNum) continue;
			for (int k = j - 1; k >= 0; k--) {
				int newResult = cardVec[i] + cardVec[j] + cardVec[k];
				if (newResult > targetNum) continue;
				else if (newResult > result) result = newResult;
			}
		}
	}

	cout << result;
}

 

느낀 점

이 문제를 푸는 다른 방법으로는 two-pointer 기법이라 하여, for문으로 카드 하나를, 나머지 두 숫자는 첫 카드보다 큰 숫자 중 가장 작은 / 큰 두 숫자로 바깥부터 조금씩 줄여나가는 방식으로 최대값을 찾는다.

이 방식을 사용하면 for문의 사용을 한 번 줄일 수 있게 되어 시간복잡도가 O(N^3) -> O(N^2) 가 될 수 있다.

 

하지만 현재의 방법 역시 예외처리를 통해 빠르게 넘어가므로 result == targetNum일 때만 break해준다면 충분히 빠른 속도를 유지할 수 있을 것으로 보아 새로 리팩토링을 하지는 않았다.

 

슬슬 C++에 익숙해져 가는 것 같다. 한동안은 알고리즘 공부를 C++로 이어가려 한다. 이유는 다음과 같다:

1. 코딩테스트에 C#을 지원하지 않는 기업이 C++를 지원하지 않는 기업보다 많다.

2. 곧 복학할 대학교에서 C#보다 C++를 주로 사용한다.

3. 메모리 관리와 성능 최적화를 공부할 때 C++이 더 도움이 될 것이다. (생성자 & 소멸자, 포인터 등)

 

아직은 VS Community의 자동완성 기능과 Ctrl+R+R 같은 단축키를 사용하고 있지만, 백준으로 C++의 사용에 조금 더 많이 능숙해지면 programmers에서 풀 타이핑으로 연습을 할 것이다.