가장 바쁜 운영 구간 · C++ 2급 | Up! COS Pro

매장 운영 시간을 같은 길이의 시간대 n개로 나눴어요. visits[i]는 i번째 시간대의 방문객 수예요. 연속된 k개 시간대를 골라 총방문객 수가 가장 많은 구간을 찾으려고 해요. 여러 구간의 총방문객 수가 같으면 더 일찍 시작하는 구간을 선택해요.

int solution(vector<int> visits, int k)가 선택한 구간의 시작 번호를 반환하도록 빈칸을 채워 주세요. 시간대 번호는 1부터 시작해요. 보조 함수 measure는 인덱스 left부터 right 직전까지의 방문객 수를 합쳐요.

매개변수와 반환값

visits의 길이 n은 1 이상 200 이하예요.
각 방문객 수는 0 이상 1,000 이하의 정수예요.
k는 1 이상 n 이하예요.
반환값은 선택한 구간의 시작 번호로, 1 이상 n - k + 1 이하예요.

예시

visits = [2, 5, 1, 4, 3], k = 2이면 1을 반환해요. 구간별 총방문객 수는 7, 6, 5, 7이고, 총수가 같은 두 구간 중 첫 구간을 선택해요.
visits = [3, 1, 3, 1], k = 2이면 1을 반환해요. 세 구간의 총수가 모두 4여서 가장 먼저 시작하는 구간을 선택해요.

실행용 입출력

main은 함수 호출용 하네스예요. 첫 줄에 n k, 둘째 줄에 방문객 수 n개를 입력하고, 반환값을 출력해요.

예시 입력

5 2
2 5 1 4 3

예상 결과

예시 입력

4 2
3 1 3 1

예상 결과

핵심 개념

array-1d: 연속 범위와 시작 위치를 구분해요.
loops: 끝 인덱스를 포함하지 않는 범위를 읽어요.
function-design: 보조 함수에 넘기는 범위의 의미를 확인해요.
stl-vector: 주어진 벡터의 크기와 인덱스로 데이터를 읽어요.

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

int measure(vector<int> visits, int left, int right) {
    int total = 0;
    for (int i = left; /*@blank1@*/; ++i) total += visits[i];
    return total;
}
int solution(vector<int> visits, int k) {
    int best = -1, position = 0;
    for (int left = 0; left + k <= (int)visits.size(); ++left) {
        int current = measure(visits, left, left + k);
        if (/*@blank2@*/) {
            best = current;
            position = left;
        }
    }
    return /*@blank3@*/;
}
int main() {
    int n, k; cin >> n >> k;
    vector<int> visits(n);
    for (int i = 0; i < n; ++i) cin >> visits[i];
    cout << solution(visits, k) << '\n';
    return 0;
}

코드 작성과 채점은 로그인 후 이용해요

로그인하고 풀기