[백준/Baekjoon] 1503 세 수 고르기 C++ :: Brute force

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

1503번: 세 수 고르기

---

1. Logic

일단 입력받은 집합에 있는 숫자를 제외해야하기 때문에 bool배열을 활용하여 제외해야 하는 숫자들을 걸러줬다.

그리고 N의 범위가 1000까지이기 때문에 브루트포싱을 돌려서 1~1001까지 3중 for문을 활용하여 풀이해줬다. 

 

시간복잡도가 1000^3 만큼 나와서 안될 줄 알았는데 내부 테케가 부족했는지 통과됐다. 이게 왜돼? 2초에 2억번 연산이라고 치면 5배나 높은 수치이다. 그래서 현재 N보다 i*j*k의 값이 크면 그 뒤의 값은 안봐도 뻔하기 때문에 가지치기를 해줬다.

문제가 약간 애매한듯?

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m;

bool arr[1001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0; i < m; i++) {
        int input;
        cin >> input;
        arr[input] = true;
    }
    
    int ans = 0x3f3f3f3f;
    
    for(int i = 1; i <= 1001; i++) {
        if(arr[i]) continue;
        for(int j = 1; j <= 1001; j++) {
            if(arr[j]) continue;
            for(int k = 1; k <= 1001; k++) {
                if(arr[k]) continue;
                int xyz = i*j*k;
                if(ans > abs(n-xyz)) ans = abs(n-xyz);
                if(n < xyz) break;
            }
        }
    }
    cout << ans;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐