백준 링크 : https://www.acmicpc.net/problem/2798

문제 개요

카드 수(n)에서 3개의 수를 뽑아 더한 후 입력으로 들어온 수(m)에 가장 가까운 합을 출력하는 문제이다.

아이디어

• 조합 알고리즘을 통해 3개의 수를 뽑은 후 더하며, max값을 계속해서 갱신한다.
  • ${n}C{3}$에 해당하는 알고리즘을 통해 n길이의 배열 중 3개의 인덱스를 뽑는다.
  • 뽑은 인덱스를 바탕으로 배열에 접근해 세 수를 더한 후 max값과 비교후 갱신한다.
• 3개를 뽑는 게 고정되어 있으므로, 조합 알고리즘을 for문으로 구현한다.

코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <iostream>
using namespace std;

int n, m, a[104], ret, sum;

int main()
{
    ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = i + 1; j < n; j++)
		{
			for(int k = j + 1; k < n; k++)
			{
				sum = a[i] + a[j] + a[k];
				if(sum <= m)
				{
					ret = max(ret, sum);
				}
			}
		}
	}
	
	cout << ret;
    return 0;
}

후기

예전에 온라인 강의에서 조합 알고리즘에 대해 배운적이 있어서, 쉽게 풀었다. 강의 내용 중에 2~3개를 뽑는 게 고정되어 있다면, for문을 통한 조합 알고리즘이 효율적이라고 했었는데, 문제를 읽자마자 그 기억이 떠올랐다.

얕은 지식이더라도 폭넓 게 아는 것은 문제 해결 속도에 많은 도움을 주는 것 같다.