[Baekjoon] 2798번: 블랙잭

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

2798번: 블랙잭

 

---

 

문제 해결 과정

착안

문제에서 주어진 \(M\)을 넘지 않으면서 \(M\)에 최대한 가까운 카드 3 장의 합을 구하기 위해서 사용할 수 있는 알고리즘이 마땅히 없다고 판단되어(일단 내가 알고 있는 바로는...), 단순하게 카드 3 장을 뽑는 모든 경우의 수에 대하여 카드 3 장의 합을 계산을 하는 알고리즘을 생각할 수 밖에 없었다. 하지만, 그렇다면 시간 복잡도(time complexity)가 \(O(N^3)\)에 달하는 엄청난 알고리즘이 되어버리기 때문에 이 문제에서는 유저에게 숨겨진 요구사항으로 '최대한 불필요한 계산을 건너뛰면서 \(O(N^3)\)의 알고리즘을 실행하라'는 것을 제시하는 것이라고 생각하였고 그에 중점을 두어 구현을 시도해봤다.

* 참고로 위와 같이 무차별적으로 다 대입하면서 해결하는 방식을 브루트 포스(brute-force) 알고리즘이라고 한다.

 

\(O(N^3)\)의 시간 복잡도를 가지는 알고리즘을 어떻게 하면 최대한 불필요한 계산을 하지 않을지 고민해 본 결과, 다음과 같은 상황이 발생했을 때에는 반복문의 실행을 제어해서 계산을 줄일 수 있을 것이라 판단하였다.

 

• 같은 카드를 중복으로 뽑는 경우(문제 기본 요구사항에 어긋남)
• 카드 3 장의 합이 정확히 M과 동일한 카드 조합을 찾는 경우
• 카드 3 장을 뽑기 전에 이미 카드의 합이 M을 초과하는 경우

 

\(N\) 장의 카드 중에서 3 개의 카드를 중복되지 않고 순서에 상관 없이 뽑는 경우의 수는 $$_{N}C_{3} = {N \choose 3} = {N(N-1)(N-2) \over 6} < N^3$$

따라서, 반복문이 중간에 break 되지 않고 최대로 실행될 때의 loop 실행 수가 \({N(N-1)(N-2)/6}\)이 되도록 반복문을 구현하고 반복문 내에서 3 장의 카드의 합이 M과 일치한 경우는 break, 카드의 합이 \(M\)을 초과할 수 밖에 없는 경우에는 continue 하여 다음 카드를 뽑도록 반복문을 제어하고자 하였다.

 

구현

삼중반복문을 이용할 때, 단순히 루프 변수 \(i ,j ,k\)를 \(0\)부터 \(N-1\)까지 반복하도록 하면 loop의 실행 횟수가 \(N^3\)이 되어 불필요한 중복 계산을 수행하게 되므로, 아래와 같이 반복문을 구현하였는데 실제로 이 반복문의 loop 실행 횟수를 수학적으로 계산했을 때 의도했던 것과 같이 동일한 횟수가 맞는지 추가로 확인해보았다.

 

// 삼중반복문 구조
for (int i = 0; i < N-2; i++)
	for (int j = i + 1; j < N-1; j++)
		for (int k = j + 1; k < N; k++)
			// do something

 

위와 같이 반복문을 구성했을 때, loop 실행 횟수는

따라서, 위에서 도출한 식을 정리해보면

$$\sum_{m = 1}^{N-2}{\sum_{n = 1}^{m}{m}} = \sum_{m = 1}^{N-2}{m(m + 1) \over 2} = {1 \over 2}\sum_{m = 1}^{N-2}{(m^2 + m)}$$

$$= {1 \over 2}\left({(N-2)(N-1)(2N-3) \over 6} + {(N-2)(N-1) \over 2}\right)$$

$$= {(N-2)(N-1) \over 2}\left({2N-3 \over 6} + {1 \over 2}\right)$$

$$= {N(N-1)(N-2) \over 6} = {N \choose 3}$$

즉, 위와 같이 반복문을 구현하는 것이 수학적으로 세 장의 카드를 중복하지 않고 뽑는 것과 같음을 확인할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;
int number = 1;

int main()
{
	int N, M, sum, result = 0;
	int nums[100] = { 0, };
	scanf("%d %d", &N, &M);

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

	for (int i = 0; i < N - 2; i++)
	{
		if (nums[i] >= M) continue;
		for (int j = i + 1; j < N - 1; j++)
		{
			if (nums[i] + nums[j] >= M) continue;
			for (int k = j + 1; k < N; k++)
			{
				sum = nums[i] + nums[j] + nums[k];

				if (sum == M)
				{
					result = sum;
					break;
				}

				if (sum < M && sum > result)
					result = sum;
			}
		}
	}
	printf("%d\n", result);

	return 0;
}

 

실행 결과

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.

 

---

 

실제로 매우 중요한 issue가 아니라면, 일일이 코딩할 때마다 저렇게 수학적으로 반복문의 횟수가 같은지 확인을 해야할 필요까지는 없다고 생각한다. 다만, 이번 문제에서 위와 같이 수학적으로 분석을 해 본 이유는 다른 사람의 코드와 비교를 해보다가 내 코드가 정말 수학적으로 논리적인 코드가 맞는지 확인을 해보고 싶었고, 단순한 문제여도 한 번쯤은 이렇게 분석을 해보는 것이 공부에 도움이 될 것 같아서 분석을 해보았다.