[백준/BOJ] 2798번, 2839번: 브루트 포스 - C++ 문제 풀이

● 2798번: 블랙잭

문제 설명

문제 링크: https://www.acmicpc.net/problem/2798

2798번: 블랙잭

 

풀이

너무 어렵게 생각할 필요 없다. 브루트 포스 방식으로 문제를 푸는 것이므로 모든 가능성이 있는 경우를 찾아서 합을 구하고, 지정된 값과 가장 가깝다면 리턴하는 문제이다.

 

그럼 첫 번째 카드 a번째 카드라고 하고, 두 번째 카드를 b번째 카드, 세 번째 카드를 c번째 카드라고 했을 때

항상 a < b < c 순서가 되도록 카드를 뽑는다면 중복되지 않고 모든 경우를 검토할 수 있다.

 

 

소스 코드

#include <iostream>
using namespace std;

int main() {
	
    int N, M;
    cin >> N >> M;

    int* cd = new int[N];
    for(int i = 0; i < N; i++){
        cin >> cd[i];
    }

    int B = 0;  // 주어진 값에 가장 가까운 값
    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++){
                
                int sum = cd[i] + cd[j] + cd[k];
                if ( sum > M) continue;		// 정해진 값보다 크면 안됨
                if ( sum > B) B = sum;		// 정해진 값에 가장 가까운 값 찾기
            }
        }
    }

    delete [] cd;

    cout << B;
    return 0;
}

---

 

 

● 2839번: 설탕 배달

문제 설명

문제 링크: https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

풀이

문제는 최소한의 설탕 봉지 개수를 원하고 있기 때문에  5킬로그램 봉지를 최대한 많이 사용할수록 전체 사용하는 설탕 봉투의 개수는 줄어들 것이다. 우선 5킬로그램을 가장 많이 사용할 수 있는 최댓값을 설정한 후, 원하는 무게를 맞추기 위해 필요한 3킬로그램 설탕 봉지의 개수를 계산하는 방식이다.

 

5킬로그램 봉지의 개수를 하나씩 줄여가며 이를 하나도 사용하지 않는 경우까지, 필요한 3킬로그램 계산하면 모든 경우의 수를 셀 수 있다. 이 경우 필요한 3킬로그램 봉지의 수를 찾을 수 없으면 -1을 리턴한다.

 

소스 코드

#include <iostream>
using namespace std;

int main() {
	
    int N, M =-1;
    cin >> N;

    int d5 = N / 5;		// 5킬로그램 봉지 최댓값
    
    for(int i = d5; i >= 0; i--){
                
        int d3 = N - i*5;	// 5킬로그램 봉지 무게를 제외한 나머지 무게

        if ( d3 % 3 != 0)
            continue;

        M = i + d3 / 3;		// 원하는 봉투의 수
        break;
    }

    cout << M;
    return 0;
}