[9주차_금요일] 행복 유치원

[Jewan1120]

• 사이트 : 백준(BOJ)
• 문제: 행복 유치원
• 번호: 13164

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[yeongleej]

🤔 시간복잡도 고려사항

• 원생 수: N ≤ 300,000
• 조의 개수: K ≤ 300,000

=> O(N * N)은 불가(X), O(N) or O(NlogN)으로 생각해보기

💡 풀이 아이디어

• 원생들이 정렬된 순서로 주어지기 때문에 차이(가장큰키-가장작은키)의 가장 작은 값은 (i+1)번쨰와 i번째의 차이가 됨
• 또한, K개의 조를 만들기 위해선 (K-1) 개의 차이를 없애야 함
• 즉, 원생들의 차이를 오름차순으로 정렬한 뒤 (K-1)개를 제외한 나머지 차이들의 합이 최솟값이 됨.
  • 차이는 (N-1)개이고 (K-1)개를 제외하면 => (N-1)-(K-1) == N-K개

[icegosimperson]

🤔 시간복잡도 고려사항

1 ≤ K, N ≤ 300,000 -> O(N)

💡 풀이 아이디어

• N명의 원생을 K개조로 나눠서 티셔츠 비용을 최소화하는 문제
• 같은 조에 속한 원생들은 서로 인접해 있어야한다 -> 인접한 원생들 간의 키 차이를 구함 -> 조를 어떻게 나누냐에 따라 전체 키 차이의 합이 달라짐 -> dff(키 차이 배열) 생성
• 같은 조에 속한 원생들은 서로 인접해야 한다 -> dffi[i] = 인접한 원생들 간의 키 차이 저장-> 오름차순 정렬
• K개의 조로 나누기 -> (K-1)개 구분선
• 티셔츠 제작 비용 최소 -> 큰 차이들을 제외하고 작은 차이들끼리 더하기

      for(int i=0; i<(N-1)-(K-1); i++){
          result += diff[i];
      }

  • (N-1) - (K-1) = N-K개

    처음에 K명씩 어떻게 할당해주지 싶었는데 diff(차이 배열)을 구해서 푸는 방법이 있더라고요..!

[KodaHye]

🤔 시간복잡도 고려사항

• 1 ≤ 원생의 수(N) ≤ 300,000
• 1 ≤ 조의 개수(K) ≤ 원생의 수
• Nlog(K) ≈ 5,458,380 인걸 고려해서 풀이해야 함

💡 풀이 아이디어

1. K개의 Deque를 만들고, 마지막 idx부터 확인하면서 최솟값과 최댓값의 차이를 줄여주는 방식 → 시간 초과
   • 최악의 경우 300,000 * 299,999 * ... * 2 * 1 이렇게 되서 그런 것 같음
2. 그리디
   • int[] diff = new int[N];
   • int result: 사용되는 비용
     • idx를 1부터 마지막 까지 탐색하며 이전값과 현재값의 차이를 구함
   • 티셔츠를 만드는 비용이 최소가 되도록 K개의 조로 만들어야 함
     • 배열 diff에서 차이가 큰 부분을 기준으로 조를 나누어서 비용이 들지 않도록 함 (Arrays.sort(diff))
     • for(int i = 0; i < N - K; i++) result += diff[i];

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 300,000
• 1 ≤ K ≤ N
• O(N) 이내

💡 풀이 아이디어

• 최대-최소차이를 가장 적게 그룹을 만들기 위해선 서로 차이가 가장 많이 나는 구간에서 그룹을 끊어줘야함
  • dif배열 : 옆사람과 차이 배열
  • dif배열 정렬 후, 상위 K-1개를 제외한 비용의 합 구하기

처음에 투포인터로 복잡하게 풀었는데,, 정렬 개념 잘 사용하기

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 300,000 → 3 x 10^5 이므로 O(N logN) 이하로 풀이

💡 풀이 아이디어

• 조원의 키 차이가 최소가 되도록 적절히 잘라줘야 함 → 키 차이가 최대가 되는 조는 잘라야 함
• 자를 수 있는 모든 경우(인접해 있는 사람과의 키 차이)를 배열로 만든 뒤 정렬해서 필요한 만큼만 뽑기
• 자른다는 것은 조를 나눈다는 것이기 때문에 정렬한 배열에서 N-K개만 선택하면 됨

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 그리디
• 시간복잡도: 1 ≤ N ≤ 300,000 그리디 순회 O(N) + 정렬 O(logN) > O(NlogN) 이내로 풀이

💡 풀이 아이디어

• 최소 비용이 나올 수 있는 최적의 조를 찾기
  • 조 편성 시 여러 경우가 있기 때문에 모든 조 편성에 대한 최소 비용을 찾을 수 없음
  • 예) 앞쪽이 대소 차가 크고 뒤쪽이 대소 차가 작을 경우 최소 비용이 나오지 않음
• 모든 원생들의 대소 차이를 구하고 최소 비용을 구하기 위해 오름차순 정렬 하기
• 이때 가장 큰 차이 값을 가지는 그룹을 제외하고 나머지 값을 모두 합산 (N-K)

왜 N-K 개 만큼의 값들을 합산하는가?

1. 초기 상태:
children 배열이 [1 3 5 6 10] 이고, 각 원소 간의 차이 값을 계산한 costs 배열은 [2 2 4 1]

2. costs 배열 정렬:
오름차순으로 정렬하면 [1 2 2 4]

3. K개의 그룹으로 나누기⭐:
예를 들어, K=3 이라고 가정하면, 3개의 그룹으로 나누기 위해서는 K-1개를 기준으로 그룹을 나눌 수 있습니다.
문제의 요구사항인 최소 비용을 구하기 위해 2개(K-1)의 가장 큰 차이 값(4와 2)을 기준으로 그룹을 나누면
[1 3], [5 6], [10] 와 같이 3개의 그룹으로 나뉘게 됩니다.

4. 작은 차이 값들 합산하기⭐:
K-1 개는 그룹을 나누는 기준이기 때문에 이를 제외하면 "(N-1)-(K-1) = N-K" 이 되고,
남은 차이 값들인 [1 2] 를 합산하면 K개의 조로 나누었을 때, 티셔츠를 만드는 최소 비용이 됩니다.