문제 링크
문제
티어: 골드 2
알고리즘: 그리디, 수학
입력
입력 파일에는 정수 N (5 ≤ N ≤ 1000)이 한 개 포함됩니다.
출력
의회가 최대한 오랫동안 운영될 수 있도록 하는 그룹의 크기를 출력하세요. 이 크기는 오름차순으로 한 줄에 출력되어야 하며, 크기 사이에는 공백으로 구분됩니다.
풀이
의회가 최대한 오랫동안 운영될 수 있도록 하는 그룹의 크기를 출력해야 한다.
최대한 오랫동안 운영된다는 건 협의 위원회를 다르게 구성할 수 있는 조합의 수를 최대로 해야함을 뜻한다.
즉, 각 그룹의 구성원 수를 곱했을 때 그 값이 최대가 되도록 그룹을 나누는 것이 핵심이다.
최대가 되도록 하려면 그룹의 구성원 수를 다르게 하면서 최대한 잘게 쪼개야 한다.
왜냐하면 그룹의 크기를 나눠서 곱하는 것이 그 곱의 값이 더 커지기 때문이다.
예를 들어 5는 2와 3에 덧셈인데 2와 3의 곱으로 변환하면 당연히 값이 최대가 된다.
그러면 구성원 수를 다르게 하면서 잘게 쪼개려면 어떻게 해야 할까?
답은 2부터 +1씩 하면서 쪼개는 것이다.
예를 들어 N이 7일 때
첫 번째 그룹은 2
두 번째 그룹은 3
그런데 세 번째 그룹은 4를 가져야 하는데 남은 수는 2가 된다.
그래서 앞에 그룹 중 하나를 선택해서 남은 수와 합쳐야 하는데, 어떤 그룹을 선택하는 것이 최적 해를 만들까?
일단 4보다 크거나 같은 값이 될 수 있는 그룹을 선택해야 한다.
그러한 그룹은 여러 개 있을 것이고, 그 중 가장 작은 구성원 수를 가진 그룹을 선택한다.
왜냐하면 현재 구성된 그룹들은 잘게 쪼개진 상태이기 때문에 최대한 그 전체 합을 유지하는 것이 최적 해를 보장하기 때문이다.
정리하자면, 현재 2 3으로 구성되어 있고, 2명이 남아 4명을 채워줄 수 없을 때 쪼개진 그룹 중 하나를 선택해서 4명 이상이 되게끔 만들어 줘야 하며 이때 4명 이상이 된 그룹은 하나의 그룹이며 덧셈인 것이고, 곱셈의 영역 중 하나의 수를 포함시키기 때문에 2를 가져오는 것이 최선의 선택이 되는 것이다.
그래서 N이 7이면 3 4가 협의 위원회를 오랫동안 구성할 수 있는 값이 된다.
이 풀이의 시간 복잡도는 O(루트N)이 된다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
ArrayList<Integer> answer = new ArrayList<>();
int nm = 2; // next member
while(N != 0) {
if(N >= nm) {
answer.add(nm);
N -= nm;
nm += 1;
} else {
//N이 nm보다 크지 않음 가장 작은 수 부터 찾아보며 nm보다 크거나 같은 최초의 지점을 찾아야됨
for(int i=0; i<answer.size(); i++) {
if(nm <= answer.get(i) + N) {
answer.add(answer.get(i) + N);
answer.remove(i);
N = 0;
break;
}
}
}
}
StringBuilder sb = new StringBuilder();
for(int i=0; i<answer.size(); i++) {
sb.append(answer.get(i)).append(" ");
}
System.out.println(sb.toString().trim());
}
}