[코드트리 챌린지] 3주차 구간 잘 나누기

https://www.codetree.ai/missions/5/problems/divide-sections-well?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

완전탐색 문제인데,, 그냥 완전탐색으로 접근하면 시간초과가 난다. 따라서 코드트리에서 강조하는 답을 정해놓고 하나씩 맞춰보는 식으로 진행해야 한다. 뭔가 문제를 많이 풀었지만,, 답을 정하고 접근하는 것과 그냥 접근하는 것의 차이를 알기 어려운 것 같다.

 

해당 코드는 해설을 보고 푼 뒤에 작성한 코드이다.

#include <iostream>
#define MAX_NUM 10000

using namespace std;
int n, m, map[100];
int main()
{
    cin >> n >> m;
    int answer = 0;
    for(int i=0; i<n; i++)
        cin >> map[i];
    for(int i=1; i<=MAX_NUM; i++){
        bool possible = true;
        int section = 1, sum =0;
        for(int j=0; j<n; j++){
            if(map[j] > i){
                possible = false;
                break;
            }
            if(map[j] + sum >i){
                sum = 0;
                section++;
            }

            sum += map[j];
        }
        if(possible && section <= m){
            cout << i;
            break;
        }
    }
    return 0;
}

 

추석이나 그 이후에 한번 더 풀어 보면 좋을 것 같다.