문제 개요
계단을 만드는 데 사용할 수 있는 벽돌의 개수 N이 주어졌을 때, 이 벽돌로 만들 수 있는 계단 단계(step)의 최대 개수를 구하는 것이 이 문제의 목표입니다.
계단을 쌓는 규칙은 다음과 같습니다.
- 첫 번째 단계는 벽돌 2개로 만듭니다.
- 그 위의 각 단계는 바로 아래 단계보다 정확히 1개 더 많은 벽돌을 사용합니다. 즉, 2개, 3개, 4개… 순으로 필요합니다.
- 남은 벽돌로 다음 단계를 만들 수 없게 되면, 그 시점까지 완성한 단계 수가 정답이 됩니다.
예시로 이해하기
입력
N = 40
출력
7
풀이 과정
단계 1 : 필요 벽돌 2개 / 누적 사용 2개 / 남은 벽돌 38개 단계 2 : 필요 벽돌 3개 / 누적 사용 5개 / 남은 벽돌 35개 단계 3 : 필요 벽돌 4개 / 누적 사용 9개 / 남은 벽돌 31개 단계 4 : 필요 벽돌 5개 / 누적 사용 14개 / 남은 벽돌 26개 단계 5 : 필요 벽돌 6개 / 누적 사용 20개 / 남은 벽돌 20개 단계 6 : 필요 벽돌 7개 / 누적 사용 27개 / 남은 벽돌 13개 단계 7 : 필요 벽돌 8개 / 누적 사용 35개 / 남은 벽돌 5개
8번째 단계를 만들려면 벽돌 9개가 필요하지만 남은 벽돌은 5개뿐입니다. 따라서 만들 수 있는 단계의 최대 개수는 7입니다.
접근 방법 1 : 단순 반복문 (O(N))
가장 직관적인 풀이는 반복문을 사용하는 것입니다. 필요한 벽돌 수를 2부터 시작해 한 단계마다 1씩 늘려 가며 남은 벽돌에서 차감하고, 더 이상 다음 단계를 만들 수 없을 때까지 진행하면 됩니다.
int findStairCount(int N){
int step = 0;
int need = 2; // 첫 단계에 필요한 벽돌 수
while (need <= N) {
N -= need; // 현재 단계에 벽돌 사용
need++; // 다음 단계는 1개 더 필요
step++;
}
return step;
}
구현이 매우 간단하지만, N이 클 경우 단계 수에 비례해 반복해야 하므로 시간 복잡도가 O(N)이 되어 비효율적일 수 있습니다.
접근 방법 2 : 합 공식과 이진 탐색 (O(log N))
k개의 단계를 만드는 데 필요한 총 벽돌 수는 등차수열의 합 공식으로 구할 수 있습니다.
필요한 총 벽돌 수 = 2 + 3 + … + (k+1) = (k+1)(k+2)/2 − 1
이 값은 k가 커질수록 단조증가하므로, 이진 탐색을 이용해 조건을 만족하는 최대 k를 빠르게 찾을 수 있습니다. 코드에서는 탐색 범위를 T = 2N으로 설정한 뒤, mid × (mid ± 1) 값을 T와 비교하며 탐색 범위를 좁혀 나가고, 최종적으로 얻은 값에서 1을 빼 실제 단계 수를 계산합니다.
C++ 구현 예제
아래 프로그램은 위 풀이가 실제로 동작하는 모습을 보여줍니다.
#include <iostream>
using namespace std;
int findStairCount(int T){
int low = 1;
int high = T / 2;
while (low <= high) {
int mid = (low + high) / 2;
if ((mid * (mid + 1)) == T)
return mid;
if (mid > 0 && (mid * (mid + 1)) > T && (mid * (mid - 1)) <= T)
return mid - 1;
if ((mid * (mid + 1)) > T)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main(){
int N = 60;
int stepCount = findStairCount(2 * N);
if (stepCount != -1)
stepCount--;
cout << "The number of stair steps that can be made is " << stepCount;
return 0;
}
실행 결과
The number of stair steps that can be made is 9
N = 60일 때, 2+3+…+10 = 54개의 벽돌로 9개의 단계를 만들 수 있고, 10번째 단계에는 11개가 필요해 만들 수 없으므로 답은 9가 됩니다.
복잡도 분석
- 시간 복잡도: 이진 탐색 풀이는 O(log N), 단순 반복문 풀이는 O(N)
- 공간 복잡도: 두 풀이 모두 O(1)
참고로 N이 매우 큰 경우 mid × (mid + 1) 연산 과정에서 int 오버플로가 발생할 수 있으므로, long long 자료형을 사용하는 것이 안전합니다.