티스토리 뷰
#. Problem
* The copyright in this matter is in Inflearn
#. Resolution Process
1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it
#. Solve
1. 총 N개의 곡, M 개의 DVD에 모든 동영상을 녹화
최소 용량의 크기를 구하라.
N개의 영상을 M 개의 DVD에 녹화할 때 최소 용량이라는 것은
9 3
1 2 3 4 5 6 7 8 9 이렇게 입력이 되었을 때,
3개의 DVD용량이 17분짜리면 (1,2,3,4,5), (6,7), (8,9) 이렇게 3개의 DVD로 녹음을 할 수 있다고 한다.
먼저, M-1번 이분을 하면 M 개의 덩어리가 생기는 것을 알 수 있는데
무슨 말이냐고라?! 1 2 3 4 5 6 7 8 9 가 있다.
이분을 해보자 (1,2,3,4,5), (6,7,8,9), 1번 이분하니까 2개의 덩어리가 생겼다.
다시 (1,2,3,4,5), (6,7), (8,9), 2번 이분하니까 3개의 덩어리가 생겼다.
여기서 우리는 최소 용량의 크기를 구해야 하므로 수가 큰 쪽으로 이분을 수행하면 된다.
3등분이 된 상태에서 8,9의 합 17분은 3개의 DVD에 모든 영상을 녹화할 수 있으므로.
그렇다면 이분탐색을 응용해서 우리는 M-1번(2번) 이분할 것이다.
1 2 3 4 5 6 7 8 9
M = 1
lt = 1, lr = 9
mid = (lt + rt) / 2 = 5
lt = mid+1 = 6
M = 2
mid (lt + rt) / 2 = 7
lt = mid+1 = 8
2번 이분을 하였으니 lt ~ rt 의 범위에 있는 수를 더한다. 8 + 9 = 17
이제 코드로 구현을 해보자!
2. 정렬된 숫자가 들어오는 줄 알았더니 아니었다ㅠㅠ
역시 착한 문제는 없는 법..
그래도 이분탐색 응용이면 정렬이 되어있어야 할텐데..
3. 결국 강사님의 힌트를 얻었는데 너무 주어진 배열에만 갇혀있었다..
1 ~ 9 까지의 합은 45 니까 1 ~ 45 사이에 답이 있는 것이므로(1개의 DVD에 담을 수 있는 최대 용량의 크기)
답의 범위를 이분검색으로 줄여야했던 것이다.
다시 적용해보자.
9 3
1 2 3 4 5 6 7 8 9
rst = 45, lt = 1, rt = 45
mid = (lt + rt) / 2 = 23
mid 의 크기로 3개의 DVD에 담을 수 있는지 확인
(1,2,3,4,5,6) (7,8) (9) 구간의 합이 23을 넘지 않을 때까지 누적합을 했을 때 3개의 덩어리가 생긴다면
23~45까지는 모두 정답이 될 수 있다는 것이다. 그러므로 1 ~ 22 사이에도 답이 있는지 확인해보자.
rst = 23, rt = 22
mid = (lt + rt) / 2 = 11
mid 의 크기로 3개의 DVD에 담을 수 있는지 확인
(1,2,3,4), (5,6), (7), (8), (9) M의 크기를 초과해버린다.
그렇다면 1 ~ 22 사이에는 정답이 없는 것이다.
다음으로 12 ~ 22 사이에 답이 있는지 확인해보자.
lt = 12
mid = (lt + rt) / 2 = 17
mid 의 크기로 3개의 DVD에 담을 수 있는지 확인
(1,2,3,4,5) (6,7), (8,9) 모두 담겼다. 그러면 12 ~ 16 사이에도 답이 있나 확인해보자
rst = 17, rt = 16
mid = (lt + rt) / 2 = 14
mid 의 크기로 3개의 DVD에 담을 수 있는지 확인
(1,2,3,4) (5,6) (7) (8) (9) M의 크기를 초과
...
이렇게 하다보면 lt 와 rt 가 엇갈리는 상황이 생기고 그렇게 되면 break; 해주면 되겠다.
그렇게되면 rst 변수에 저장되어있던 17이 정답이 된다.
생각의 폭을 더 넓게 가져보자ㅠㅠ
#. Code
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int main(void) { freopen("input.txt", "rt", stdin); int n, m, i, lt = 1, rt, mid, sum = 0, rst, cnt; scanf("%d %d", &n, &m); vector<int> vt(n + 1); for (i = 1; i <= n; i++) { scanf("%d", &vt[i]); sum += vt[i]; } rt = sum; rst = sum; while (lt <= rt) { mid = (lt + rt) / 2; sum = 0; cnt = 1; for (i = 1; i <= n; i++) { sum += vt[i]; if (sum > mid) { sum = vt[i]; cnt++; } } if (cnt <= m) { rt = mid - 1; rst = mid; } else if (cnt > m) lt = mid + 1; } printf("%d\n", rst); return 0; } | cs |
강사님의 힌트를 얻고 다시 풀어본 코드이다.
반례로 인해 기존 코드에 약간의 소스를 더 추가해주어야 한다
9 9
1 2 3 4 5 6 7 8 9
이렇게 입력을 했을 때,
결과로 9가 나와야 하는데 1이 나와버린다.
그 이유는 if(sum > mid) 에서 sum이 DVD 의 size(mid) 보다 크면 true 로 넘어버린다.
그렇기때문에 size가 1일 경우, 하나의 DVD에 있는 한 곡의 길이가 9가 나오더라도 true로 넘어가버리므로 결과가 1이 나와버린다.
이 반례를 잡아내기 위해서는 곡들 중 최대 길이의 곡을 알아야 하고,
size 는 최소한 최대 길이의 곡보다는 커야 한다는 조건을 추가해주어야 할 것이다.
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int main(void) { freopen("input.txt", "rt", stdin); int n, m, i, lt = 1, rt = 0, mid, sum = 0, rst, cnt, max = -2147000000; scanf("%d %d", &n, &m); vector<int> vt(n + 1); for (i = 1; i <= n; i++) { scanf("%d", &vt[i]); sum += vt[i]; max = vt[i] > max ? vt[i] : max; } rt = sum; rst = sum; while (lt <= rt) { mid = (lt + rt) / 2; sum = 0; cnt = 1; for (i = 1; i <= n; i++) { sum += vt[i]; if (sum > mid) { sum = vt[i]; cnt++; } } if (mid >= max && cnt <= m) { rt = mid - 1; rst = mid; } else lt = mid + 1; } printf("%d\n", rst); return 0; } | cs |
#. Other code
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int a[1001], n; int Count(int s) { int i, cnt = 1, sum = 0; for (i = 1; i <= n; i++) { if (sum + a[i] > s) { cnt++; sum = a[i]; } else sum = sum + a[i]; } return cnt; } int main(void) { int m, i, lt = 1, rt = 0, mid, res; scanf("%d %d", &n, &m); for (i = 1; i <= n; i++) { scanf("%d", &a[i]); rt = rt + a[i]; } while (lt <= rt) { mid = (lt + rt) / 2; if (Count(mid) <= m) { res = mid; rt = mid - 1; } else lt = mid + 1; } printf("%d\n", res); return 0; } | cs |
반례 수정 코드
입력 시 max 값을 저장해두고
count 의 개수가 m보다 작거나 같으면서,
mid 가 max 보다 크거나 같을 경우의 조건이 추가되었다.
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include<stdio.h> #include<algorithm> using namespace std; int a[1001], n; int Count(int s){ int i, cnt=1, sum=0; for(i=1; i<=n; i++){ if(sum+a[i]>s){ cnt++; sum=a[i]; } else sum=sum+a[i]; } return cnt; } int main(){ int m, i, lt=1, rt=0, mid, res, maxx=-2147000000; scanf("%d %d", &n, &m); for(i=1; i<=n; i++){ scanf("%d", &a[i]); rt=rt+a[i]; if(a[i]>maxx) maxx=a[i]; } while(lt<=rt){ mid=(lt+rt)/2; if(mid>=maxx && Count(mid)<=m){ res=mid; rt=mid-1; } else lt=mid+1; } printf("%d\n", res); return 0; } | cs |
#. Result
- Input --------------------------------------------------------
9 3
1 2 3 4 5 6 7 8 9
------------------------------------------------------------------
- Output --------------------------------------------------------
17
------------------------------------------------------------------
'PS > Problem_Solving' 카테고리의 다른 글
| [Inflearn] 멀티태스킹 (0) | 2020.04.28 |
|---|---|
| [Inflearn] 마구간 정하기(binary search apply) (0) | 2020.04.27 |
| [Inflearn] 연속된 자연수의 합 (0) | 2020.04.26 |
| [Inflearn] 두 배열 합치기 (0) | 2020.04.24 |
| [Inflearn] Inversion Sequene (0) | 2020.04.24 |