[알고리즘] 완전 탐색 기본편

boms·2024년 3월 4일
1
post-thumbnail

문제 풀이 및 생각 과정을 정리한 글입니다


모든 상황에 대해 값 설정하기

[난이도 하] 야바위

https://www.codetree.ai/missions/5/problems/ya-rock/introduction

  • 세 컵이 있을 때 N번에 걸쳐 a번 종이컵과 b번 종이컵을 교환한 뒤, c번 종이컵을 열어 그 안에 조약돌이 있으면 점수를 얻는 행동을 반복한다

  • 조약돌을 어느 컵에 넣어야 최대 점수를 얻을 수 있을까?

  • 1 ≤ N ≤ 100

  • 1 ≤ a, b, c ≤ 3, a ≠ b

컵이 세개 밖에 없고 N이 충분히 작기 때문에 모든 경우를 테스트한다.
1. 조약돌을 넣을 i번 인덱스 고르는 for문
2. a번과 b번을 교체하는 swap 함수 (⭐️ swap 함수 활용)
3. c번에 조약돌이 있는지 확인하고 count
4. 매번 for문 끝날때 count 최대 구하기

[난이도 하] 중첩 완전탐색

https://www.codetree.ai/missions/5/problems/multiply-two-and-remove-one-number/introduction

  • n개의 숫자가 주어졌을 때, 하나의 숫자를 선택해 2배를 한 후, 다시 하나의 숫자를 선택해 제거하여 남은 n - 1개의 원소 중 인접한 숫자간의 차의 합이 최소가 되도록 하는 프로그램을 작성해보세요
  • 3 ≤ n ≤ 100
  • 1 ≤ 주어지는 숫자 ≤ 100

N이 작기 때문에 모든 경우를 테스트한다.
1. 두배할 i번 인덱스 고르는 for문
2. 제거할 j번 인덱스 고르는 for문
3. j번 인덱스을 제외하고 새로운 vector에 저장
4. 인접한 숫자간의 차의 합을 구하고 최소 구하기
⭐️ 1번 for문 처음에 2배 했으므로 끝에 나누기 2 해주기

[난이도 중하] 3개의 선

https://www.codetree.ai/missions/5/problems/balance-on-coordinate-plane-2/description

  • 좌표평면 위에 서로 다른 N개의 점이 주어졌을 때, x축 혹은 y축에 평행한 직선 3개로 주어진 모든 점들을 전부 지나게 할 수 있는지를 판단하는 프로그램을 작성해보세요.

  • 1 ≤ N ≤ 20

  • 0 ≤ x, y ≤ 10

선 세개를 그어서 주어진 n개의 점을 다 통과하는지 확인해야한다. 선이 그어지는 범위가 충분히 작기 때문에 완전탐색한다.
1. x축, y축에 그은 선 세개의 모든 경우의 수를 3중 for문을 사용하여 구한다
2. n개의 점을 순환하며 다음을 확인하고 갯수를 센다

  • x축에 그은 선 세개 중에 하나가 점을 지나가는 지
  • x축에 그은 선 2개와 y축에 그은 선 1개 중에 하나가 점을 지나가는 지
  • x축에 그은 선 1개와 y축에 그은 선 2개 중에 하나가 점을 지나가는 지
  • y축에 그은 선 3개 중에 하나가 점을 지나가는 지
  1. 해당 선 세개가 지나는 점 갯수가 N개면 전부 지날 수 있다고 판단한다

[유사문제] 좌표평면 위의 균형

https://www.codetree.ai/missions/5/problems/balance-on-coordinate-plane-2/description

  • x축과 y축에 선 하나씩 그었을 때 4구간 중 가장 많은 점의 수가 최소가 되도록 할 때 점의 수를 구하는 문제
  • 3개의 선 문제와 유사하게 이중 for문으로 모든 선을 테스트한다.

[난이도 중하] 틱택토

https://www.codetree.ai/missions/5/problems/tic-tac-to-as-a-team-2/description

  • 오목과 유사한 틱택토 게임이다. 여러명이서 게임을 진행한 3X3 결과물이 주어진다. 만약 두명이서 팀을 먹었을 때 팀으로 이길 수 있는 가짓수를 구하기.
  • 개개인을 1~9 번호 나타낸다

두명이서 팀을 먹는 것이 핵심이다. 게임 판과 개인 번호 범위가 충분히 작기 때문에 두명이서 팀을 먹는 모든 경우의 수를 탐색한다.
1. 이중 for문으로 모든 팀 구성(i,j)를 탐색한다.
2. 승리 조건은 다음과 같다

  • 가로 줄에 i,j가 있음
  • 세로 줄에 i,j가 있음
  • 왼쪽 위에서 오른쪽 아래로 대각선에 i,j가 있음
  • 오른쪽 위에서 왼쪽 아래로 대각선에 i,j가 있음
  1. i,j가 있는지 확인하기 위해서는 i,j를 따로 countI, countJ에 출연 횟수를 세고 countI+countJ==3 이면서 countI>=1 이고 countJ>=1이면 된다.
    ⭐️ countI+countJ==3: 한줄에 I,J가 둔 수가 정확이 세개있다 = 팀 먹으면 승
    ⭐️ countI>=1, countJ>=1: i와 j가 최소 1번 출연. i혹은 j 한명이서 3번 나오는건 팀으로 승리하는게 아니다.

[난이도 중하] 등장하지 않는 문자열의 길이

https://www.codetree.ai/missions/5/problems/length-of-string-that-does-not-appear/description

  • 대문자 알파벳(A~Z)으로만 이루어지고 길이가 N인 문자열이 주어짐
  • 주어진 문자열의 연속 부분문자열로서 2번 이상 등장하는 문자열이 없는 길이 중 최솟값을 구하기.

2번 이상 등장하지 않는 부분문자열 중 길이가 최솟값인 것을 구해아한다. 즉 길이가 1인 부분문자열부터 모두 탐색해가며 모두 실패하는 문자열 길이를 구하면된다.
1. 모든 부분문자열을 각각의 길에 해당하는 set에 저장한다.
2. for문을 통해 부분문자열을 길이를 탐색하며 해당 set에 저장한 부분문자열이 두번 이상 등장하는지 확인한다.
3. 두번 이상 등장하지 않는 부분문자열을 찾는 즉시 해당 길이를 반환한다.
⭐️ 길이 1부터 확인했기 때문에 제일 먼저 찾은 부분문자열의 길이가 최솟값이다.

set을 사용하지 않고 길이 i 부분문자열 구하는 방법

for(int i=1;i<=n;i++){

        bool dup = false;
        
        for(int j=0;j<=n-i;j++){
        
            for(int k=j+1;k<=n-i;k++){
                
                for(int l=0;l<i;l++){
                
                    if(s[j+l]==s[k+l]) dup = true;
                    
                }
            }
        }
        if(dup==false){
            cout << i;
            break;
        }

    }
  • 부분문자열 길이 i
  • j번째 index부터 부분문자열 시작
  • k번째 index부터 부분문자열 찾기
    • ⭐️ 부분문자열이 또 나오는지 탐색하려면 해당 부분문자열 첫번째 인덱스 바로 다음인 j+1 부터 시작해야한다
  • j와 k로 부분문자열들의 시작 인덱스를 구했으니 각각 오른쪽으로 i개 만큼 서로 일치하는지 확인한다

구간 단위로 완전탐색

[난이도 하] 구간 중 최대 합

https://www.codetree.ai/missions/5/problems/max-sum-of-subarray/description

  • n개의 숫자들이 주어졌을 때, 연속하여 k개의 숫자를 골랐을 때의 최대 합 구하기
int answer = 0;
for(int i=0;i<n-k+1;i++){
        int sum = 0;
        for(int j=i;j<i+k;j++){
            sum += v[j];
        }
        answer = max(answer,sum);
    }
  • 시작점을 i로 잡고 길이가 k일 때
  • i<n-k+1 : 양쪽 포함일 때 +1

[난이도 하] 특정 구간의 원소 평균값

https://www.codetree.ai/missions/5/problems/elemental-mean-value-for-a-particular-interval/introduction

  • N개의 숫자가 주어지고, 특정 구간을 잡았을 때 그 구간 안에 있는 원소들의 평균값이 그 구간의 원소 중 하나가 되는 서로 다른 가짓수 구하기
int cnt = 0;
    // 시작
    for(int i=0;i<n;i++){
        // 끝
        for(int j=i;j<n;j++){
            int sum = 0;
            for(int k=i;k<=j;k++){
                sum+=arr[k];
            }

            // 평균
            double avg = (double) sum / (j-i+1);

            bool exist = false;
            for(int k=i;k<=j;k++){
                if(arr[k]==avg){
                    exist = true;
                    break;
                }
            }
            if(exist) cnt++;
        }
    }
    cout << cnt;
  • 구간 중 최대 합 문제에서는 시작점 j=i로 잡고 j+길이 까지 확인함
  • 이 문제는 평균을 구하기 때문에 시작점과 끝점을 먼저 잡는게 더 좋아보임
  • 평균 구할때는 double 자료형 사용하기
  • double == int 가능하다

[난이도 중하] 바구니 안의 사탕

https://www.codetree.ai/missions/5/problems/candy-in-the-basket-2/description

  • 1차원 직선 위에 총 N개의 바구니가 놓여 있고, 바구니 안에는
    사탕이 담겨 있습니다. 중심점 c를 잘 잡아 [c-K, c+K] 구간에 있는 최대 사탕의 수 구하기

첫번째 접근

    for(int i=0;i<=MAX_N-2*k;i++){
        int cnt = 0;
        for(int j=0;j<=2*k;j++){
            cnt += arr[i+j];
        }
        max_cnt = max(max_cnt,cnt);
    }
    cout << max_cnt;
  • 어차피 구간으로 합을 구하기 때문에 중심 c가 아닌 첫번째 인덱스를 모두 탐색하기로함
  • 사실 문제에서 안주어졌지만 구간이 0 과 구간 최대값을 벗어나면 포함되는 구간에 대해서만 합을 구해야함. 근데 해당 코드는 구간을 절대로 벗어나지 않음.

두번째 접근

    for(int i=0;i<=MAX_N;i++){
        int cnt = 0;
        for(int j=i-k;j<=i+k;j++){
            if(j>=0 && j<=MAX_N) cnt += arr[j];
        }
        max_cnt = max(max_cnt,cnt);
    }
    cout << max_cnt;
  • 중심 c의 모든 인덱스를 탐색하기로함
  • if(j>=0 && j<=MAX_N) : 유효한 구간에 있는 수들을 합할 수 있도록 조건 추가함

[난이도 중하] 아름다운 수열

  • N개의 숫자로 이루어진 수열 A와 M개의 숫자로 이루어진 수열 B가 주어진다. 수열 B의 각 원소들의 순서를 바꿔 나오는 수열을 아름다운 수열이라고 한다. 수열 A에서 길이가 M인 연속 부분 수열들 중 아름다운 수열의 수를 구하여라
#include <iostream>
#include <algorithm>
#define MAX_N 100
#define MAX_M 100
using namespace std;

int n,m;
int arr_n [MAX_N];
int arr_m [MAX_M];
int temp [MAX_M];

int main() {

    cin >> n >> m;

    for(int i=0;i<n;i++){
        cin >> arr_n[i];
    }
    for(int i=0;i<m;i++){
        cin >> arr_m[i];
    }

    sort(arr_m,arr_m + m); // 수열 B 정렬

    int cnt = 0;
    for(int i=0;i<n-m+1;i++){
        for(int j=0;j<m;j++){
            temp[j] = arr_n[i+j];
        }
        sort(temp,temp+m); // 수열 A를 구간 M으로 탐색하여 담은 수열을 정렬

        bool match = true;
        for(int k=0;k<m;k++){
            if(temp[k]!=arr_m[k]){
                match = false;
                break;
            }
        }
        if(match) cnt ++;
    }
    cout << cnt;
    return 0;
}

수열 B의 순열이 수열 A 안에 몇개가 있는지 구하면된다. 먼저 모든 순열을 구하고 A의 모든 인덱스를 돌며 찾으려고 했는데 더 빠른 방법이 생각났다.
⭐️ 순열을 구할 필요없이 정렬을 사용하자!
수열의 순열이란 수열안 숫자들을 배치할 수 있는 모든 경우의 수다. 모든 순열을 어느 한 기준 (오름차순 혹은 내림차순)으로 정렬하면 전부 다 같은 결과가 나온다. 따라서 수열 B를 오름차순으로 정렬한 것을 수열 A를 구간 길이 M으로 탐색하여 오름차순으로 정렬한 것을 비교하면 된다!

자리 마다 숫자를 정하는 완전탐색

[난이도 하] 개발자의 능력 3

https://www.codetree.ai/missions/5/problems/ability-of-developer-3/description

  • 개발자 6명의 알고리즘 능력을 수치화해 각각 정수로 주어지면 6명을 3명씩 2팀으로 배정해준다. 팀원들의 능력 총합간의 차이를 최소화 할 수 있게 균형있게 구성해줄 때의 차를 구하기.
#include <iostream>
#define MAX_ARR 6
using namespace std;

int arr[MAX_ARR];

int main() {
    int total_sum = 0;
    for(int i=0;i<MAX_ARR;i++){
        cin >> arr[i];
        total_sum+=arr[i];
    }

    int min_diff = 1e9;

    for(int i=0;i<MAX_ARR;i++){
        for(int j=i+1;j<MAX_ARR;j++){
            for(int k=j+1;k<MAX_ARR;k++){
                int sum = arr[i]+arr[j]+arr[k];
                min_diff = min (min_diff, abs(total_sum-sum-sum));
            }
        }
    }
    cout << min_diff;
    return 0;
}
  • 세명씩 두팀이기 때문에 세 인덱스를 i<j<k 범위로 구하고 탐색하면 쉽게 구할 수 있다
  • 하지만 두팀보다 많다면?

[난이도 중하] 개발자의 능력 2

https://www.codetree.ai/missions/5/problems/ability-of-developer-2/explanation

  • 위 문제와 비슷하지만 이번에는 두명씩 세팀이다

첫번째 접근

#include <iostream>
#define MAX_ARR 6
using namespace std;

int arr[MAX_ARR];

int main() {
    int sum = 0;
    for(int i=0;i<MAX_ARR;i++){
        cin >> arr[i];
        sum += arr[i];
    }
    int total_min = 1e9;
    for(int i=0;i<MAX_ARR;i++){
        for(int j=i+1;j<MAX_ARR;j++){
            for(int k=j+1;k<MAX_ARR;k++){
                for(int l=k+1;l<MAX_ARR;l++){
                    int sum_one = arr[i]+arr[j];
                    int sum_two = arr[k]+arr[l];
                    int sum_three = sum - sum_one - sum_two;
                    int max_team = max(sum_one,max(sum_two,sum_three));
                    int min_team = min(sum_one,min(sum_two,sum_three));
                    
                    total_min = min(total_min, max_team-min_team);
                }   
            }
        }
    }
    cout << total_min;
    return 0;
}
  • 개발자의 능력 2와 똑같이 i<j<k<l 범위로 인덱스를 골랐지만 이 방식은 잘못됐다!
  • 위 방식은 모든 경우의 수를 탐색하지 않음으로 완전탐색이 아니다
  • 예를 들어 첫번째 인덱스와 마지막 인덱스가 같은 팀이 되는 경우가 불가능하다. 이유는 j가 마지막 인덱스가 되면 k, l값이 MAX_ARR 이상이 되어 for문이 닫혀 그냥 넘어간다.

두번째 접근

#include <iostream>
#define MAX_ARR 6
using namespace std;

int arr[MAX_ARR];

int main() {
    int sum = 0;
    for(int i=0;i<MAX_ARR;i++){
        cin >> arr[i];
        sum += arr[i];
    }
    int total_min = 1e9;
    for(int i=0;i<MAX_ARR;i++){
        for(int j=0;j<MAX_ARR;j++){
            for(int k=0;k<MAX_ARR;k++){
                for(int l=0;l<MAX_ARR;l++){
                    if(i==j || i==k || i== l || j==k || j==l || k==l) continue;
                    int sum_one = arr[i]+arr[j];
                    int sum_two = arr[k]+arr[l];
                    int sum_three = sum - sum_one - sum_two;
                    int max_team = max(sum_one,max(sum_two,sum_three));
                    int min_team = min(sum_one,min(sum_two,sum_three));
                    
                    total_min = min(total_min, max_team-min_team);
                }   
            }
        }
    }
    cout << total_min;
    return 0;
}
  • 모든 경우의 수를 구하기 위해서 0< i,j,k,l <MAX_ARR로 범위를 잡고 서로 겹치지 않도록 조건을 추가했다

자리 수 단위로 완전탐색

[난이도 하] 이상한 진수

https://www.codetree.ai/missions/5/problems/awkward-digits-2/description

  • 0 이상의 정수 N을 2진법으로 나타낸 뒤, 그 숫자들 중 정확히 한 숫자만을 바꾼 숫자 a가 주어졌을 때, 가능한 숫자 N 중 최댓값 찾기
#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int i;
    for(i=0;i<s.size();i++){
        if(s[i]=='0'){
            s[i]='1';
            break;
        }
    }
    if(i==s.size()){
        s[s.size()-1]='0';
    }
    int num = 0;
    for(int i=0;i<s.size();i++){
        num+=(s[s.size()-i-1]-'0')*pow(2,i);
    }

    cout << num;

    return 0;
}
  • 2진수를 최대한 크게하려면 왼쪽에서부터 첫 0을 찾아 1로 바꾸면된다
  • 다 1이면 맨 오른쪽 1 (2^0) 자리를 0으로 바꾸면 최소한으로 바꿀 수 있다.

[난이도 중하] 마라톤 중간에 택시타기 2

https://www.codetree.ai/missions/5/problems/taking-a-taxi-in-the-middle-of-the-marathon-2/description

  • 마라톤 코스 체크포인트 N개가 있을때 1개를 뺄 수 있다. 1개를 빼서 총 거리가 최소가 되도록 만들기
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int,int> pii;

int main() {
    vector<pii>v;
    int n;
    cin >> n;

    for(int i=0;i<n;i++){
        int x,y;
        cin >> x >> y;
        v.push_back({x,y});
    }

    int answer = 1e9;
    // 건너뛸 점 선택
    for(int i=1;i<n-1;i++){
        int dist = 0;
        int prev = 0;
        for(int j=1;j<n;j++){
            if(j==i) continue;
            dist += abs(v[prev].first - v[j].first) + abs(v[prev].second - v[j].second);
            prev = j;
        }
        answer = min(answer,dist);
    }
    cout << answer;
    return 0;
}
  • 가장 고민이 많았던 부분은 어떻게 하면 for문을 돌며 특정 인덱스를 제외하고 인접 차를 구할지 였다
  • ⭐️ 건너뛰기 위해 prev 인덱스 기억하기!
  • j가 건너뛰는 인덱스가 되면 prev를 갱신하지 않고 j만 1커지도록 하면 prev를 건너뛰는 인덱스 이전, j를 건너뛰는 인덱스 이후로 가르킬 수 있다.

[난이도 중하] 원 모양으로 되어있는 방

  • 원 모양으로 되어있는 N개의 방이 있고, 방은 1부터 N까지 시계 반대방향으로 번호가 매겨져 있습니다.
  • 각 방에는 이웃한 두 개의 방으로 통하는 문이있다.
  • 사람들은 무조건 시계 반대방향으로만 이동해야 한다.
  • 각자 방에 몇 명이 사람이 들어가야하는지 주어지며, 모든 사람이 같은 방에서 시작한다고 합니다. - - 어떤 방에서 시작해야 각 방에 정해진 인원이 들어가는 데까지의 거리의 합을 최소화 할 수 있는지 구하여라
#include <iostream>
using namespace std;
int main() {
    int n;
    int map[1004];
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> map[i];
    }

    int ans = 1e9;
    for(int i=1;i<=n;i++){
        int dist_sum = 0;
        for(int j=1;j<=n;j++){
            int dist = (j+n-i)%n;
            cout << i << " " << j << " " << dist << endl;
            dist_sum+=dist*map[j];
        }
        ans = min(ans,dist_sum);
    }
    cout << ans;
    

    return 0;
}
  • 1~n이 반시계로 돌 때 거리를 어떻게 구할지 고민했다
  • ⭐️ i에서 j로 갈 때 반시계 방향은 (j+n-i)%n
  • ⭐️ i에서 j로 갈 때 시계 방향은 (i+n-j)%n
  • 방향이 상관 없다면?
    - https://www.codetree.ai/missions/5/problems/a-two-way-lock/description
    - ⭐️⭐️ i에서 j로 갈 때 방향이 상관 없을 때 거리가 k 이하?
    • abs(i-j) <= k || abs(i-j) >=n-k

[난이도 중] Carry 피하기

https://www.codetree.ai/missions/5/problems/escaping-carry-2/description

-n개의 숫자가 주어지고, 그 중 정확히 서로 다른 3개의 숫자를 골랐을 때 carry가 전혀 발생하지 않으면서 나올 수 있는 숫자 합의 최댓값을 계산하는 프로그램을 작성해보세요.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n;
    int map[20];
    int num;

    cin >> n;
    for(int i=0;i<n;i++){
        cin >> map[i];
    }

    int answer = -1;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int k=j+1;k<n;k++){
                bool carry = false;
                //일의 자리
                if(map[i]%10+map[j]%10+map[k]%10>=10) carry = true;
                //십의 자리
                if(map[i]%100/10+map[j]%100/10+map[k]%100/10 >=10) carry = true;
                //백의 자리
                if(map[i]%1000/100+map[j]%1000/100+map[k]%1000/100>=10) carry = true;
                //천의 자리
                if(map[i]%10000/1000+map[j]%10000/1000+map[k]%10000/1000>=10) carry = true;

                if(!carry) answer = max(answer,map[i]+map[j]+map[k]);
                
            }
        }
    }
    cout << answer;
    return 0;
}
  • 주어진 숫자들의 길이가 다 다른데 어떻게 자릿수 합을 구할지 고민했다
  • 일의 자리는 %10
  • 십의 자리는 %100)/10
  • 백의 자리는 %1000)/100
  • 즉 %로 더 큰 자리수들을 없애고 /로 맨앞 숫자를 추출한다

[난이도 하] 오목

  • 오목 결과를 보고 승자 (1 혹은 2) 와 이긴 수의 중간 좌표 구하기
#include <iostream>
using namespace std;


int main() {
    int map[19][19];

    int dx[] = {-1,-1,-1,1,1,1,0,0};
    int dy[] = {-1,0,1,-1,0,1,-1,1};
    for(int i=0;i<19;i++){
        for(int j=0;j<19;j++){
            cin >> map[i][j];
        }
    }
    int answer = 0;
    for(int i=0;i<19;i++){
        for(int j=0;j<19;j++){

            if(map[i][j]==0) continue;

            for(int k=0;k<8;k++){
                int cnt = 1, curI = i, curJ = j;
                while(true){
                    int ni = curI+dy[k];
                    int nj = curJ+dx[k];
                    if(nj<0 || nj>=19 || ni<0 || ni>=19) break;
                    if(map[ni][nj] != map[i][j]) break;
                    
                    cnt++;
                    curI = ni;
                    curJ = nj;
                }
                if(cnt==5){
                    cout << map[i][j] << '\n';
                    cout << i + 2*dy[k] + 1 << " " << j + 2*dx[k] + 1;
                    return 0;
                }
            }
        }
    }
    cout << 0;
}
  • 오묵을 둘 수 있는 방향은 총 8가지이므로 모든 좌표에 대해 8 방향을 체크한다
  • 연속인지 확인하기 위해 curI, curJ를 해당 방향 다음 좌표로 최신화한다
  • 계속해서 승리 수인지 확인할 방법은
    - 유효한 범위인지 확인한다
    - 시작 인덱스의 오목색과 같은 오목색인지 체크한다

기준을 새로 설정하여 완전탐색

https://www.codetree.ai/missions/5/problems/study-cafe-keeping-distance-5/description

  • 비어있는 좌석(0)에 한 사람을 앉힐 때 앉아있는 사람들(1)이 최대한 거리를 둬야한다. 이때 가능한 최대 거리값을 구하여라
#include <iostream>
#define MAX_N 20
using namespace std;

string seat;
int n;
int main() {
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> seat;
    }
    int max_count = 0;
    for(int i=0;i<n;i++){
        if(seat[i]=='1') continue;
        seat[i] = '1';
        int count = MAX_N;
        for(int j=0;j<n;j++){
            bool flag = false;
            for(int k=j+1;k<n;k++){
                if(seat[j] == '1' && seat[k] == '1'){
                    count = min(count,k-j);
                    flag = true;
                }
                if(flag) break;
            }
        }
        max_count = max(max_count,count);
        seat[i] = '0';
    }
    cout << max_count;
    return 0;
}
  • 가장 가까운 사람들의 거리들을 구하고 이 거리들의 최대값을 구하면된다.
  • 가장 가까운 사람들의 거리를 구하기 위해 이중 for문으로 1 두개를 찾고 인덱스 차로 거리를 갱신하도록 했다.
  • seat string을 다 순회하지 않고 j 기준 가장 가까운 1 k를 찾으면 바로 다음 j,k 쌍을 찾기위해 flag를 사용했다.
profile
2023.08.21~

0개의 댓글