[코드트리] 완전탐색 / 자리 수 단위로 완탐 연습문제

 

5개의 숫자 [1, 5, 2, 6, 8]이 주어졌을 때
이 중 단 하나의 숫자만 두 배로 해서, 인접한 숫자간의 차이의 합이 최대가 되도록 해보세요.

 

위 문제는 단순하게, 모든 위치의 숫자를 2배씩 해보는 완전탐색을 진행해 볼 수 있습니다.

1. 첫 번째 숫자 1에 2배를 하는 경우
[2, 5, 2, 6, 8]이 되므로, 인접한 숫자간의 차이의 합은 3 + 3 + 4 + 2 = 12가 됩니다.

2. 두 번째 숫자 5에 2배를 하는 경우
[1, 10, 2, 6, 8]이 남게 되므로, 인접한 숫자간의 차이의 합은 9 + 8 + 4 + 2 = 23이 됩니다.

3. 세 번째 숫자 2에 2배를 하는 경우
[1, 5, 4, 6, 8]이 남게 되므로, 인접한 숫자간의 차이의 합은 4 + 1 + 2 + 2 = 9가 됩니다.

4. 네 번째 숫자 6에 2배를 하는 경우
[1, 5, 2, 12, 8]이 남게 되므로, 인접한 숫자간의 차이의 합은 4 + 3 + 10 + 4 = 21이 됩니다.

5. 다섯 번째 숫자 8에 2배를 하는 경우
[1, 5, 2, 6, 16]이 남게 되므로, 인접한 숫자간의 차이의 합은 4 + 3 + 4 + 10 = 21이 됩니다.

따라서 최대는 23이 됩니다.

 

 

이처럼 각 자리에 대해 상황을 일일이 가정해보고 진행해보는 완전탐색 방법을 이용하면, 문제를 깔끔하게 해결할 수 있습니다.

 

만약 최댓값을 구하는 완전탐색 코드가 있다고 가정합시다.

그러면 max_val 값의 초기값은, 들어올 수 있는 값들보다 훨씬 작은 값으로 잡아야 합니다.
이 경우에 max_val에 첫 번째 원소를 초기값으로 넣어준 뒤 진행하는 방법도 있지만,
완전탐색 유형에서는 첫 번째 원소 값을 구하는 것 자체가 간단하지 않기 때문에, 초기값으로 아주 작은 값을 잡아 주는 것이 좋습니다.

 

최댓값을 구해주는 경우에는 다음과 같이 #include <climits>를 추가하여 max_val에 INT_MIN 값을,

최솟값을 구해주는 경우에는 min_val에 INT_MAX를 초기값으로 넣어주는 과정이 필요합니다.

 

---

연습문제 : 모이자

n개의 집이 x = 1에서 x = n까지 순서대로 놓여있고, 각각 Ai​ 명의 사람이 살고 있습니다. 이들은 회의를 위해 n개의 집 중 한 곳에 전부 모이려고 합니다. 적절한 집을 선택하여 모든 사람들의 이동 거리의 합이 최소가 되도록 하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 n이 주어집니다.
두 번째 줄에는 각 지점에 살고 있는 사람 수에 해당하는 n개의 숫자가 공백을 사이에 두고 주어집니다.

• 1 ≤ n ≤ 100
• 1 ≤ Ai​ ≤ 100

출력 형식

가능한 이동 거리의 합 중 최솟값을 출력합니다.

---

나의 풀이

#include <iostream>
#include <climits>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    int people[101] = {0,};
    cin>>n;
    for(int i=0; i<n; ++i){
        cin >> people[i];
    }
    int sum = 0;
    int answer = INT_MAX;
    for(int i=0; i<n; ++i){
        sum = 0;
        for(int j=0; j<n; ++j){
            if(j==i) continue;
            int d = abs(j-i);
            sum += people[j]*d;
        }
        if(answer > sum) answer = sum;
    }
    cout << answer;
    return 0;
}

 

완탐에서 min / max 선언시에는 정수값의 최대/최소를 넣어두는 걸 잊지말자!