프로그래머스 쿠키 구입 C언어

1. 무작정 for문을 돌려봤는데 정말 시간 복잡도가 쉣이ㅏ다.

아예 cookie 배열에서 n번째까지의 합을 따로 sum이라는 배열에 저장했다. 

그러면 첫째 아들은 sum[m] - sum[l] 둘째 아들은 sum[r] - sum[m+1] 을 가져간다.

 

2. 처음에는 sum, cookie 배열에서 for문을 0부터 시작하는지 1부터 시작하는지 너무 헷갈렸다.

아래와 같이 진행되는 것을 자꾸 파악하지 못해서 헤맸다. 

i	0	1	2	3	4
sum[i]	0	1	2	4	7
cookie[i]	1	1	2	3

 

3. 두 번째 for문에서 첫째 아들의 sum[m]을 결정하고

세 번째 for문에서는 둘째 아들의 시작점은 m+1로 정해져 있으므로 m[r]을 결정한다.

네 번째 for문에서는 둘째 아들의 쿠키 갯수가 정해지고 나서 그 갯수에 맞춰서 첫째 아들의 시작점 l 을 결정한다.

 

 

4. 아무리 sum으로 시간 복잡도를 줄여도 for문이 4개나 있고 배열의 크기가 최대 2000 이라는 점에서 시간 복잡도가 여전히 크다. 

 

     (1) if문 

second_son 의 갯수는 변하지 않는 반면에 first_son의 갯수는 sum[l] 만큼 빼야한다.

그러므로 애초에 second_son의 갯수가 first_son보다 큰 것은 탈락

 

어차피 answer에는 기존 answer 값과 second_son 중에 최대값이 들어가므로 answer > second_son인 경우도 탈락

 

     (2) break;

첫째 아들의 l 값을 결정하는 for 문에서 if 문 조건을 만족했다면 해당 for문을 나와도 된다.

어차피 l 값이 증가해봤자 answer 보다 값이 작아지므로 비교할 필요가 없다.

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
int sum[2001];
 
// cookie_len은 배열 cookie의 길이입니다.
int solution(int cookie[], int cookie_len) {
    int answer = 0;
    
    for (int i = 0;i < cookie_len; i++){
       sum[i+1] = sum[i] + cookie[i];
    }
    
    for (int m = 1; m < cookie_len; m++){
        int first_son = sum[m];
 
        for(int r = m+1; r <= cookie_len; r++){
            int second_son = sum[r] - sum[m];
            
            if(answer > second_son || second_son > first_son) continue;
            
            for(int l = 0; l < m; l++){
                if(first_son - sum[l] == second_son && answer < second_son){
                    answer = second_son;
                    break;
                }
            }
        }
    }
 
    return answer;
}