C++로 돌을 나눠줄 수 있는 최대 횟수 계산하는 방법

숫자 n이 주어졌다고 가정해 봅시다. 아말(Amal)은 비말(Bimal)에게 돌을 여러 번에 걸쳐 나누어 줍니다. 단, 한 차례에서 k개의 돌을 주었다면 바로 다음 차례에는 k개를 줄 수 없습니다. 즉, 연속된 두 차례에서 주는 돌의 개수는 반드시 서로 달라야 합니다. 우리가 구해야 할 것은 아말이 비말에게 돌을 줄 수 있는 총 횟수입니다.

예를 들어 입력이 n = 4라면 출력은 3이 됩니다. 처음에 1개, 그다음에 2개, 마지막에 다시 1개를 주면 총 4개의 돌을 세 번에 나누어 줄 수 있기 때문입니다.

풀이 접근

이 문제는 다음 공식 하나로 간단히 해결할 수 있습니다 −

return (n * 2 + 1) / 3

왜 이 공식이 성립할까?

주는 횟수를 최대화하려면 매 차례 가능한 한 적은 수의 돌을 주면서, 동시에 이전 차례와 다른 개수를 유지해야 합니다. 따라서 1개와 2개를 번갈아 주는 것이 최적 전략입니다. 이 패턴에서는 두 차례마다 3개의 돌이 소모되므로 전체 횟수는 대략 2n/3이 되고, 경계 조건까지 고려한 정확한 값은 (2n + 1) / 3의 정수 나눗셈 결과와 일치합니다.

예제 구현

더 나은 이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다 −

#include <bits/stdc++.h>
using namespace std;
int solve(int n){
   return (n * 2 + 1) / 3;
}
int main(){
   int n = 4;
   cout << solve(n) << endl;
}