💡 PS
[BOJ] 2613 숫자구슬
date
Feb 21, 2022
slug
boj-2613
author
status
Public
tags
PS
이분탐색
summary
숫자구슬에 대한 풀이입니다.
type
Post
thumbnail
category
💡 PS
updatedAt
Aug 3, 2023 08:57 AM
언어
문제
풀이
만약 이 문제를 완전탐색으로 푼 다면, N-1개의 지점 중 M-1개를 뽑는 중복조합 문제이다. 그럴 경우 시간이 무지하게 많이 걸릴 것이다.
아마 이 문제의 힌트는 구슬에 적힌 수가 비교적 작다는 것이 아닐까 싶다.
나는 이를 이분탐색으로 풀었다.
구슬을 여러 집합으로 나눌 때, 각 그룹에 포함된 구슬의 개수를 이분탐색의 범위로 잡는다는 아이디어가 어려웠다.
탐색 범위의 최소값(
l)은 해당 배열 중 최대값이다. 최대값(r)은 원소의 총 합이다.searchAns() 함수에서 이분탐색을 진행한다.getNum(int mi)에서는 중간값(mi)을 넘지 않으면서 만들 수 있는 집합의 최소 개수이다. 만약, 이 값이 m보다 클 경우 mi가 더 커져야 하므로 l을 mi + 1로 수정한다. 그렇지 않을 경우, r을 mi로 수정한다.이분탐색이 끝나고 난
r이 문제에서 원하는 첫번째 출력값이다.이젠 m개의 집합으로 나누었을 때 각 집합에 들어있는 구슬의 개수를 출력해야 한다. 여기서 중요한 점이 한가지 있다.
아래와 같은 예시를 보자.
Input
7 4
1 1 1 4 1 1 1우선 각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때 그 최댓값은 4이다. 하지만 4개의 그룹보다 적게 구슬이 배치될 수도 있다.(3개 4개 3개)
이를 고려해주면서 두번째 줄을 출력해주어야 한다. 나같은 경우, 39번째 줄을 추가하여 i번째를 포함한 이후의 구슬 개수가 추가로 출력해주어야 개수와 같다면 바로 출력하도록 하였다.
코드
#include <cstdio> #include <algorithm> using namespace std; int n, m, l = 0, r = 0; int arr[300]; int getNum(int mi) { int ret = 0, tmp = 0; for(int i = 0; i < n; i++) { if (tmp + arr[i] >= mi) { if (tmp + arr[i] == mi) tmp = 0; else tmp = arr[i]; ret++; } else tmp += arr[i]; } return tmp > 0 ? ret+1 : ret; } void searchAns() { while (l < r) { int mi = (l + r) / 2; if (getNum(mi) <= m) r = mi; else l = mi + 1; } printf("%d\n", r); int tmp = 0, t = 0, cnt = 0; for(int i = 0; i < n; i++) { if (tmp + arr[i] > r) { printf("%d ", t); cnt++; t = 1; tmp = arr[i]; } else if (tmp + arr[i] == r){ printf("%d ", t + 1); cnt++; t = 0; tmp = 0; } else if (n-i == (m-cnt)){ printf("%d ", t + 1); cnt++; t = 0; tmp = 0; } else { tmp += arr[i]; t++; } } if (t != 0) printf("%d", t); } int main() { scanf("%d %d", &n, &m); for(int i = 0; i < n; i++) { scanf("%d", &arr[i]); l = max(l, arr[i]); r += arr[i]; } searchAns(); }