문제 개요
크기가 K인 배열 A가 있다고 가정해 보겠습니다. 이 게임에는 N명의 어린이와 게임 진행자가 등장하며, 게임은 총 K라운드로 구성됩니다. i번째 라운드에서 진행자는 A[i]명씩 그룹을 만들라고 선언합니다. 그러면 남아 있는 어린이들은 A[i]명으로 구성된 그룹을 최대한 많이 만들고, 한 명의 어린이가 여러 그룹에 동시에 속할 수는 없습니다. 그룹에 속하지 못한 어린이는 게임에서 탈락하며, 나머지는 다음 라운드로 진출합니다. 물론 탈락자가 한 명도 발생하지 않는 라운드도 있을 수 있습니다. 최종적으로 K번째 라운드가 끝난 후 정확히 두 명의 어린이만 남게 되며, 이들이 우승자로 선언됩니다. 우리가 구해야 할 것은 게임 시작 전 존재할 수 있는 어린이 수의 최솟값과 최댓값이며, 만약 유효한 N이 존재하지 않는다면 그 사실을 판별해야 합니다.
예시
예를 들어 입력이 A = [3, 4, 3, 2]라면 출력은 [6, 8]이 됩니다. 게임이 6명의 어린이로 시작한다면 다음과 같이 진행됩니다.
1라운드: 6명이 3명씩 두 그룹을 만듭니다. (탈락자 없음)
2라운드: 6명 중 4명이 하나의 그룹을 만들고, 나머지 2명은 탈락합니다.
3라운드: 4명 중 3명이 그룹을 만들고, 1명은 탈락합니다.
4라운드: 3명 중 2명이 그룹을 만들고, 1명은 탈락합니다.
마지막에 남은 2명이 우승자로 선언됩니다.
접근 방법: 역추적
이 문제는 최종 상태에서 출발하여 거꾸로 거슬러 올라가는 역추적(backtracking) 방식으로 효율적으로 해결할 수 있습니다. 핵심 관찰은 다음과 같습니다. 어떤 라운드가 끝난 후 남은 인원은 반드시 해당 라운드의 그룹 크기 x의 배수여야 합니다. 따라서 마지막 라운드부터 첫 번째 라운드까지 순서대로 거슬러 올라가며, 각 단계에서 가능한 인원 범위 [l, r]를 갱신합니다.
최솟값 갱신: 현재 하한 l 이상이면서 x의 배수인 가장 작은 수는 ⌈l / x⌉ × x 입니다.
최댓값 갱신: 현재 상한 r 이하이면서 x의 배수인 가장 큰 수는 ⌊r / x⌋ × x 이며, 직전 라운드의 인원은 이 값에 x − 1을 더한 범위까지 허용됩니다.
갱신 과정에서 최솟값이 최댓값보다 커지는 순간(L > R)이 발생하면 조건을 만족하는 N이 존재하지 않으므로 −1을 출력합니다. 초기값은 최종적으로 2명이 남아야 하므로 l = r = 2로 설정합니다.
알고리즘 단계
n := 배열 A의 크기
l := 2, r := 2 // 최종적으로 2명이 남아야 함
i := n 부터 1까지 1씩 감소시키며 반복:
x := A[i]
L := ⌈l / x⌉ × x // l 이상인 x의 배수 중 최소값
R := ⌊r / x⌋ × x // r 이하인 x의 배수 중 최대값
만약 L > R 이면:
유효한 값이 없으므로 -1 출력 후 종료
l := L, r := R + x - 1
반복이 끝나면 l과 r을 출력
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A){
int n = A.size();
long long l = 2, r = 2;
for (int i = n; i >= 1; i--){
long long x = A[i - 1];
long long L = (l + x - 1) / x * x; // l 이상인 x의 배수
long long R = r / x * x; // r 이하인 x의 배수
if (L > R){
cout << "-1, 0";
return;
}
l = L;
r = R + x - 1;
}
cout << l << ", " << r << endl;
}
int main(){
vector<int> A = { 3, 4, 3, 2 };
solve(A);
}
입력
{ 3, 4, 3, 2 }출력
6, 8
복잡도 분석
각 라운드를 한 번씩만 처리하므로 시간 복잡도는 O(K)이며, 추가 메모리 사용량은 O(1)입니다. 배열의 길이가 매우 크더라도 빠르게 답을 구할 수 있는 효율적인 알고리즘입니다.