문제 이해하기
세 개의 정수 y, b, r이 주어집니다. 각각 노란색 장식 y개, 파란색 장식 b개, 빨간색 장식 r개를 의미합니다. 장식이 '아름답다'고 판단되려면 다음 조건을 만족해야 합니다.
- 사용된 파란색 장식의 개수는 노란색 장식의 개수보다 정확히 1개 더 많아야 합니다.
- 사용된 빨간색 장식의 개수는 파란색 장식의 개수보다 정확히 1개 더 많아야 합니다.
즉, 노란색 장식을 n개 사용한다면 파란색은 n+1개, 빨간색은 n+2개를 사용해야 합니다. 우리의 목표는 이 조건을 지키면서 가능한 한 많은 장식을 사용하는 것이며, 그때의 총 장식 개수를 구하는 것입니다.
예를 들어 입력이 y = 8, b = 13, r = 9라면 출력은 24가 됩니다. 노란색 7개 + 파란색 8개 + 빨간색 9개 = 24이기 때문입니다.
접근 방법
노란색 장식을 n개 사용하려면 보유량 제약 때문에 다음 세 조건을 동시에 만족해야 합니다.
- n ≤ y
- n + 1 ≤ b, 즉 n ≤ b − 1
- n + 2 ≤ r, 즉 n ≤ r − 2
따라서 n의 최댓값은 y, b−1, r−2 세 값 중 가장 작은 값이 됩니다. 이때 총 장식 개수는 3n + 3이므로, 다음 공식 하나로 답을 바로 계산할 수 있습니다.
return 3 * min(y, min(b - 1, r - 2)) + 3;
예제 코드
아래 C++ 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int y, int b, int r){
return 3 * min(y, min(b - 1, r - 2)) + 3;
}
int main(){
int y = 8;
int b = 13;
int r = 9;
cout << solve(y, b, r) << endl;
}
입력
8, 13, 9
출력
24
복잡도 분석
이 풀이는 단순히 세 값 중 최솟값을 구한 뒤 곱셈과 덧셈만 수행하므로, 시간 복잡도와 공간 복잡도가 모두 O(1)입니다. 입력 크기와 무관하게 일정한 시간 안에 정답을 얻을 수 있는 매우 효율적인 방법입니다.