백준 2798 C++

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

2798번: 블랙잭

 

알고리즘 스터디 하는 친구가 가져온 문제가 백트래킹 문제들인데

브루트 포스 개념조차 기억이 안 나서... ㅠㅠ

개념 리마인드 겸 브루트 포스 문제의 대명사인 블랙잭 문제를 다시 풀어보고자 한다

 

브루트 포스의 종류

1. 순차 탐색 - 선형 구조를 순차적으로 탐색
2. DFS(깊이 우선 탐색) - 비선형구조를 점점 더 깊게 깊이를 우선적으로 탐색하는 방법
3. BFS(너비 우선 탐색) - 비선형구조를 너비를 기준으로 탐색하는 방법

선형 구조인지 비선형 구조인지에 따라 풀이 방법이 달라진다!

• 선형 구조 : 순차 탐색
• 비선형 구조 : 백트래킹, DFS, BFS

선형 구조 브루트 포스 문제 푸는 방법

1. 주어진 문제를 선형 구조로 구조화 한다.
2. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
3. 구성된 해를 정리한다.

-> 선형 구조로 구조화 한다는 의미 : 문제에서 주어진 상황을 컴퓨터가 풀기 쉽게 정리하면 되는 것!

 

비선형 구조 문제 풀이 방법은 다른 문제를 풀면서 알아보고! 일단 블랙잭은 선형 구조 문제로 그냥 무식하게 풀면 된다

비선형 구조처럼 구조화 할 필요 없이 그냥 for문 세 번 돌리면 된다!

 

 

코드

#include <iostream>
using namespace std;

int main() {
    int n, m, card[100];
    int sum=0, max=0;
    cin >> n >> m;
    
    for(int i=0 ; i<n ; i++){
        cin >> card[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 = card[i] + card[j] + card[k];
                if(sum > max && sum <= m){
                    max = sum;
                }
            }
        }
    }
    cout << max;
}

 

 

뭔가 예전이 더 잘 풀었던 것 같다

지금의 난 쓰레기야...

메모리는 배열 선언을 n으로 받고의 차이여서 차이가 납니당