문제 설명
N명의 학생과 각 학생이 획득한 점수를 담고 있는 배열이 주어집니다. 학교는 학생들에게 상품으로 테디 곰을 나눠주기로 결정했지만, 비용을 절약하기 위해 다음 조건들을 만족하면서 배분해야 할 테디의 총 개수를 최소화하려고 합니다.
- 모든 학생은 최소 한 개의 테디를 받아야 합니다.
- 두 학생이 나란히 앉아 있을 때, 더 높은 점수를 받은 학생이 반드시 더 많은 테디를 받아야 합니다.
- 두 학생의 점수가 같다면 서로 다른 개수의 테디를 받아도 괜찮습니다.
예시
학생이 3명이고, 점수가 배열로 다음과 같이 주어진다고 가정해 보겠습니다.
arr[] = {2, 3, 3}
테디 배분 결과: {1, 2, 1} → 총 4개의 테디 필요
가운데 학생이 양옆 학생보다 점수가 높으므로 2개를 받고, 나머지 두 학생은 조건을 만족하는 최솟값인 1개씩 받게 됩니다.
알고리즘
이 문제는 동적 프로그래밍(Dynamic Programming) 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 절차는 다음과 같습니다.
1. 크기 N인 테이블을 생성하고, 모든 학생이 최소 한 개씩은
받아야 하므로 전체를 1로 초기화합니다.
2. 점수 배열을 순회하면서 아래 작업을 수행합니다.
a. 현재 학생의 점수가 바로 앞 학생보다 높은 경우:
i. 앞 학생에게 지급된 테디 개수를 확인합니다.
ii. 그 값에 1을 더해 현재 학생의 테디 개수로 저장합니다.
b. 현재 학생의 점수가 바로 앞 학생보다 낮은 경우:
i. 조건이 만족될 때까지 이전에 할당된 값들을
역방향으로 검토하고 수정합니다.
C++ 구현 코드
#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int teddieDistribution(int *marks, int n) {
int table[n];
fill(table, table + n, 1);
for (int i = 0; i < n - 1; ++i) {
if (marks[i + 1] > marks[i]) {
table[i + 1] = table[i] + 1;
} else if (marks[i] > marks[i + 1]) {
int temp = i;
while (true) {
if (temp >= 0 && (marks[temp] >
marks[temp + 1])) {
if (table[temp] >
table[temp + 1]) {
--temp;
continue;
} else {
table[temp] =
table[temp + 1] + 1;
--temp;
}
} else {
break;
}
}
}
}
int totalTeddies = 0;
for (int i = 0; i < n; ++i) {
totalTeddies += table[i];
}
return totalTeddies;
}
int main() {
int marks[] = {2, 6, 5, 2, 3, 7};
int totalTeddies = teddieDistribution(marks,
SIZE(marks));
cout << "Total teddies to be distributed: " <<
totalTeddies << "\n";
return 0;
}
실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 출력이 생성됩니다.
Total teddies to be distributed: 12
동작 원리 분석
입력 배열 {2, 6, 5, 2, 3, 7}에 대해 알고리즘이 계산한 최종 배분표는 다음과 같습니다.
점수: {2, 6, 5, 2, 3, 7}
테디: {1, 3, 2, 1, 2, 3} → 총합 12
오름차순 구간에서는 앞 학생의 테디 개수에 1을 더해 그대로 확정하지만, 내림차순 구간(예: 6 → 5 → 2)에서는 이미 부여된 값을 뒤에서부터 되돌아가며 조건을 위반하지 않는 선에서 최소한으로 증가시킵니다. 이렇게 하면 모든 인접 조건을 만족하면서도 전체 테디 수를 최소로 유지할 수 있습니다.
시간 복잡도는 내림차순 구간을 역방향으로 재조정하는 과정 때문에 최악의 경우 O(N²)이며, 추가로 사용되는 메모리는 길이 N의 테이블 하나뿐이므로 공간 복잡도는 O(N)입니다.