17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야

흩날리는 시험지 속에서 내 평점이 느껴진거야

 

시간 제한            메모리 제한           제출           정답           맞힌 사람           정답 비율

 

1 초

256 MB

1516

636

500

48.685%

문제

넓은 시험 범위와 어려운 과제로 유명한 '운영체제로 보는 데이터베이스시스템 알고리즘' 수업은 시험지가 너무 많아 실내에서는 시험을 치를 수 없어서 야외에서 시험을 진행한다. 해당 수업의 수강생인 현수는 오랜 시간에 걸쳐 풀 수 있는 모든 문제를 풀었고 제출만을 남겨두고 있었다. 그러나 갑자기 불어오는 강풍에 현수의 시험지가 모두 날아가 버렸고, 날아간 시험지를 줍는 동안 남은 시간을 다 써버리고 말았다.

시험지에 명시된 규칙 중에는 채점하는 조교의 편의를 위해 시험지를 반드시 순서대로 제출하라는 규칙이 있는데, 이 규칙 때문에 현수는 힘들게 치른 시험이 0점 처리될 위기에 빠지게 되었다!

그러나, 마음씨 좋은 조교인 주찬이는 평소 수업에 열심히 참여한 현수에게 한 번의 기회를 주기로 했다. 규칙은 규칙이므로 많은 점수를 줄 수는 없고, 시험지를 현재 순서 그대로 K개의 그룹으로 나눈 뒤 각각의 그룹에서 맞은 문제 개수의 합을 구하여 그 중 최솟값을 시험 점수로 하기로 하였다. 현수가 이번 시험에서 받을 수 있는 최대 점수를 계산하는 프로그램을 작성하자.

현수는 모르는 문제를 아예 풀지 않기 때문에 현수가 푼 문제는 모두 맞았다고 생각할 수 있으며, 조교는 마음씨가 좋아서 자신이 줄 수 있는 최대한의 점수를 준다.

입력

 

첫 번째 줄에 시험지의 개수 N과 시험지를 나눌 그룹의 수 K가 정수로 주어진다. (1 ≤ K ≤ N ≤ 105)

두 번째 줄에 각 시험지마다 맞은 문제의 개수 x가 정수로 주어진다 (0 ≤ x ≤ 20)

출력

현수가 받을 수 있는 최대 점수를 출력한다.

예제 입력 1 복사

8 2
12 7 19 20 17 14 9 10

예제 출력 1 복사

50

시험지를 12, 7, 19, 20과 17, 14, 9, 10 으로 나누면 맞은 문제 개수의 합의 최소는 50이다.

 

 

https://doorrock.tistory.com/54

[백준 17951번] 흩날리는 시험지 속에서 내 평점이 느껴진거야

 

스터디에서 설명을 듣고, 블로그 코드를 보며 공부했다.

 

저 분 코드와 같다!!!! 주석만 친절히 붙여놨다..

#include <bits/stdc++.h>
using namespace std;

int N,K, l , r, mid, temp,s, a[100000];
vector<int> v;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> N >> K;
    for(int i=0;i<N;i++){
        cin >> a[i];
        s += a[i]; //합계 구함
    }
    //2. 이분탐색 수행
    l=0; r=s; //0부터 원소의 모든 합
    while(l<=r){
        mid = (l+r)/2; //시험 문제 최소합
        //그룹 나누기
        int sum=0; int cnt=0;
        for(int k=0;k<N;k++){ //시험지 개수만큼 반복
            sum += a[k];
            if(sum>=mid){
                sum=0;
                cnt++; //그룹 수 +1
            }
        }
        if(cnt >=K){ //그룹 수가 K보다 더 많이 쪼개지면
            l=mid+1; //더 큰 수로 나눈다.
        }
        else r=mid-1;
    }
    //3. 정답 출력
    cout << r <<"\n"; //마지막으로 구한 최소합(가장 크다.)

}