문제 개요
하나의 숫자 n이 주어졌을 때, 이를 합이 n이 되도록 양의 정수들의 내림차순(비증가) 수열로 분할할 수 있습니다. 이때 분할의 가중치(weight)란 분할을 이루는 요소 중 첫 번째 요소와 값이 같은 요소의 개수를 의미합니다.
몇 가지 예를 들어 보겠습니다.
- 분할 [1,1,1,1,1]의 가중치는 5입니다.
- 분할 [5,5,3,3,3]의 가중치는 2입니다.
- 분할 [9]의 가중치는 1입니다.
우리가 구해야 할 것은 숫자 n의 모든 분할에서 나타날 수 있는 서로 다른 가중치의 개수입니다.
예시
입력이 n = 7이라면 출력은 4가 됩니다. 서로 다른 가중치를 가지는 대표적인 분할은 다음과 같습니다.
- [7] → 가중치 1
- [3, 3, 1] → 가중치 2
- [2, 2, 2, 1] → 가중치 3
- [1, 1, 1, 1, 1, 1, 1] → 가중치 7
풀이 접근 방식
이 문제는 생각보다 단순한 수학적 규칙으로 해결할 수 있습니다. n의 분할에서 나올 수 있는 가중치는 다음과 같이 정리됩니다.
- 가중치 1: [n]처럼 요소가 하나뿐인 경우
- 가중치 2 ~ ⌊n/2⌋: 같은 값이 반복되는 형태의 분할로 만들 수 있습니다.
- 가중치 n: [1, 1, ..., 1]처럼 모든 요소가 1인 경우
따라서 가능한 가중치의 총 개수는 다음 식 하나로 구할 수 있습니다.
return (n / 2 + 1);
즉, 복잡한 완전 탐색 없이도 상수 시간(O(1))에 답을 계산할 수 있습니다.
C++ 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int n){
return (n / 2 + 1);
}
int main(){
int n = 7;
cout << solve(n) << endl;
}
입력
7
출력
4
n = 7을 입력했을 때 결과값 4가 출력되며, 이는 앞서 살펴본 네 가지 서로 다른 가중치와 일치합니다. 이처럼 규칙성만 파악하면 아주 간단한 한 줄 코드로 문제를 해결할 수 있습니다.