매일프로그래밍 구독을 저번주에 시작했다.
첫번째로 나온 문제가 제목의 문제와 같아 채점 겸 코딩을 해보았다.
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
| #include<stdio.h> int main() { int T, N; int arr[1001]; int d[1001]; int max; int c, i; scanf("%d", &T); for (c = 0; c < T; c++) { scanf("%d", &N); for (i = 0; i < N; i++) { scanf("%d", &arr[i]); } d[0] = arr[0]; max = d[0]; for (i = 1; i < N; i++) { d[i] = d[i - 1] + arr[i] > arr[i] ? d[i - 1] + arr[i] : arr[i]; max = max > d[i] ? max : d[i]; } printf("%d\n", max); } return 0; }
|
대략 20분 정도의 고민을 한 거 같은데, 아래와 같은 키 포인트를 발견하는 것에 대부분의 시간이 걸렸다.
0~i번째까지의 max-subarray 는 i-1번째까지의 max-subarray + i번째 값 또는 그냥 i번째 값이다.
나머지 코딩은 그냥 쉬운 일차원 DP였다.
푸는 문제마다 다 DP인 거 같다. 아무래도 공식만 알아내면 코딩이 안 귀찮아서 그런 것 같다. 그다지 좋은 경향은 아닐 것이다.
