프로그래머스 쿠키 구입 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 보다 값이 작아지므로 비교할 필요가 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#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;
}
|