양의 정수 N이 주어졌을 때, 이 숫자를 3개의 부분으로 나눌 수 있는 모든 방법의 수를 구하는 것이 목표입니다. 각 부분은 서로 같아도 되고 달라도 되며, N의 범위는 [1, 5000]입니다.
이 문제는 세 개의 for 반복문을 사용해 해결할 수 있습니다. 숫자의 세 부분에 해당하는 값을 하나씩 탐색하면서, 가장 안쪽 반복문에서 세 값의 합이 N과 같은지 확인합니다. 합이 N과 일치하면 방법의 수(count)를 1씩 증가시킵니다.
예제로 이해하기
입력 − N = 5
출력 − N을 3부분으로 나누는 방법의 수: 2
설명 − 5는 (1, 1, 3)과 (1, 2, 2) 두 가지 조합의 합으로 표현할 수 있습니다.
입력 − N = 9
출력 − N을 3부분으로 나누는 방법의 수: 7
설명 − 9는 다음과 같이 표현할 수 있습니다: (1, 1, 7), (1, 2, 6), (1, 3, 5), (1, 4, 4), (2, 2, 5), (2, 3, 4), (3, 3, 3)
알고리즘 접근 방식
- 1부터 5000 사이의 값으로 초기화된 정수 N을 입력받습니다.
- 함수 divideN(int n)은 n을 받아 n을 3부분으로 나누는 방법의 수를 반환합니다.
- 방법의 수를 저장할 변수 count를 0으로 초기화합니다.
- 숫자의 각 부분을 탐색하기 위해 세 개의 for 반복문을 사용합니다.
- 가장 바깥쪽 루프는 1 ≤ i < n, 중간 루프는 i ≤ j < n, 가장 안쪽 루프는 j ≤ k < n 범위로 설정합니다.
- i + j + k의 합이 n과 같은지 확인하고, 참이면 count를 증가시킵니다.
- 모든 반복문이 종료되면 count에는 n을 세 부분으로 나누는 총 방법의 수가 저장됩니다.
- count를 결과로 반환합니다.
여기서 중간 루프와 안쪽 루프의 시작점을 각각 i와 j로 설정한 이유는 (1, 2, 3)과 (3, 2, 1)처럼 순서만 다른 중복 조합을 제거하기 위해서입니다. 이렇게 하면 오름차순 조합만 세어지므로 정확한 결과를 얻을 수 있습니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
int divideN(int n){
int count = 0;
for (int i = 1; i < n; i++){
for (int j = i ; j < n; j++){
for (int k = j; k < n; k++){
int sum=i+j+k;
if(sum==n)
{ count++; }
}
}
}
return count;
}
int main(){
int N=500;
cout <<endl<< "Number of ways to divide N in 3 parts : "<<divideN(N);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Number of ways to divide N in 3 parts: 20833
N = 500일 때 세 부분의 합이 500이 되는 오름차순 조합은 총 20,833가지입니다. 이 방법은 시간 복잡도가 O(N³)이므로 N이 최대 5000까지 가능하지만, 더 큰 입력값에는 수학적 공식을 활용한 최적화를 고려하는 것이 좋습니다.