은행 금고에서 훔칠 수 있는 최대 지폐 수를 계산하는 C++ 코드

문제 설명

세 개의 숫자 k, l, m과 n개의 원소를 가진 배열 A가 주어졌다고 가정해 보겠습니다. 한 강도가 은행 강도 시도에는 실패했지만, 은행의 모든 금고를 여는 데는 성공했습니다. 이 실패한 강도 사건을 틈타 어떤 사람이 금고에서 돈을 훔치려 합니다.

금고들은 일렬로 늘어서 있으며, 모든 금고에는 총 n장의 지폐가 남아 있습니다. i번째 지폐는 A[i]번 금고에 들어 있습니다. 현재 은행 직원은 k번 금고에 있으며, 경비원 두 명이 배치되어 있습니다. 한 명은 l(k보다 작음)번 금고를 지키고 있어 왼쪽에 위치하고, 다른 한 명은 m(k보다 큼)번 금고를 지키고 있어 오른쪽에 위치합니다. 두 경비원은 움직이지 않습니다.

매 초마다 이 사람은 현재 금고의 모든 지폐를 가져가거나 인접한 금고로 이동할 수 있습니다. 단, 도난 혐의를 피하기 위해 경비원이 지키는 금고는 어떤 경우에도 방문할 수 없습니다. 우리는 이 사람이 모을 수 있는 지폐의 최대 개수를 구해야 합니다.

예를 들어 입력이 k = 5, l = 3, m = 7, A = [4, 7, 5, 5, 3, 6, 2, 8]이라면 출력은 4가 됩니다. 경비원이 지키는 3번과 7번 금고를 제외하고, 그 사이에 있는 4, 5, 5, 6번 금고의 지폐만 가져올 수 있기 때문입니다.

풀이 접근

이 문제를 해결하기 위해 다음 단계를 따릅니다 −

핵심 아이디어는 간단합니다. 경비원이 지키는 l번과 m번 금고 사이(l보다 크고 m보다 작은 위치)에 있는 금고만 자유롭게 방문할 수 있으므로, 배열 A를 순회하면서 그 범위에 속하는 지폐의 개수를 세면 됩니다.

c1 := 0
n := size of A
c1 := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
    x := A[i]
    if x > l and x < m, then:
        (increase c1 by 1)
return c1

예제

다음 구현을 통해 더 잘 이해해 보겠습니다 −

#include <bits/stdc++.h>
using namespace std;
int solve(int k, int l, int m, vector<int> A){
    int c1 = 0, x;
    int n = A.size();
    c1 = 0;
    for (int i = 0; i < n; i++){
        x = A[i];
        if (x > l && x < m)
            c1++;
    }
    return c1;
}
int main(){
    int k = 5;
    int l = 3;
    int m = 7;
    vector<int> A = { 4, 7, 5, 5, 3, 6, 2, 8 };
    cout << solve(k, l, m, A) << endl;
}

입력

5, 3, 7, { 4, 7, 5, 5, 3, 6, 2, 8 }