이번에 풀어볼 문제는 어떤 자연수 N $( 1 \leq N \leq 10,000,000)$ 를 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 찾아내는 문제입니다. 이 문제에서 내가 했던 고민들과 틀렸던 과정들을 서술하면서 마지막에는 어떻게 수정하였는지 코드를 통해서 알려드리도록 하겠습니다.
문제
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶어 한다. 이때, 사용하는 자연수는 N이하여야 한다.
예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. N을 입력받아 가짓수를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 정수 N이 주어진다.
출력
입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 출력하시오
처음 생각 및 풀이과정
- N + 1 개의 long type 부분합을 먼저 구하자 (N이 $10^7$이므로 제한시간 2초 안에 하려면 $O(N^2)$알고리즘은 안될 듯? + 그리고 부분합 최대를 하면 $N^2 = 10^{14}$이므로 long형태의 부분합 array를 만들어야 함)
- 투포인터(아직 제대로 모름)를 활용해서 부분합 array에서 포인터 위치(i, j) (0, 0)에서 (0, 1)로 증가하면서 N값을 넘기면 (1, 1)로 이동 부분합 N을 찾으면 counter++
- 그런 형태를 계속해서 반복하면 끝까지 안 가도 되니까 $O(N^2)$ 정도는 아니지 않을까?
- 끝까지 반복하다가 끝까지 가면 종료
코드
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif // !_CRT_SECURE_NO_WARNIGS
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(void)
{
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int num;
int counter = 0;
cin >> num;
vector<long> prefix_array(num + 1, 0);
for (int i = 1; i <= num; ++i) {
prefix_array[i] = prefix_array[i - 1] + i;
}
for (int i = 0; i < num + 1; ++i) {
for (int j = 0; j < num + 1; ++j) {
if (prefix_array[j] - prefix_array[i] == num) {
counter++;
}
else if (prefix_array[j] - prefix_array[i] > num) {
break;
}
}
}
cout << counter << "\n";
return 0;
}
문제점
여기서 정답으로 처리가 되었으면 좋았겠지만, 이렇게 코드를 작성하니 메모리 초과가 났다. 이 문제에서 메모리 제한은 32MB인데 내가 작성한 코드를 대략적으로 생각해 보면 최대 N의 값을 기준으로 대략적으로 $10^7 * 8 byte = 80 MB$ (실제는 $10^7 * 8 / 1024^2 = 76.29MB$
)여서 long 타입의 부분합으로 나타내면 안 될 것 같다고 생각이 들었다.
다시 생각해 본 해결방법
이 문제를 다시 해결하기 위해서 고민한 방법은 1부터 2,3,4를 차례대로 더하다가 N이 만들어지면 counter++, N이 초과하면 앞에 수를 하나 줄이고 다시 뒤로 진행을 한다. (예를 들면 N = 15, 1 + 2 + 3 + 4 + 5를 해서 counter++하고 1 + 2 + 3 + 4 + 5 + 6 하면 N을 초과하므로 맨 앞에 있는 1을 빼고 다시 계산을 해본다. 2 + 3 + 4 + 5 + 6 = 20 이므로 다시 2를 빼고 3 + 4 + 5 + 6 = 18, 4 + 5 + 6 = 15 결과를 찾았으니 counter증가 이런 방식을 반복하는 형태)
- first_ptr, last_prt, sum을 모두 1로 설정을 한다.
- sum이 num(=N)보다 작으면 last_ptr을 1 증가시켜서 sum에 더한다.
- sum이 num(=N)보다 크면 sum에 first_ptr를 빼고 난 뒤 first_ptr을 1 뺀다.
- sum이 num이랑 같으면 counter를 증가시킨다.
- 그리고 last_ptr을 1 증가시키고 sum에 더한다.
- 이를 last_ptr 이 num을 초과할 때까지 반복(항상 first_ptr <= last_ptr이므로 last_ptr기준으로만 하면 된다.)
- counter 출력
코드
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif // !_CRT_SECURE_NO_WARNIGS
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(void)
{
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int num;
int counter = 0;
int first_ptr = 1;
int last_ptr = 1;
int sum = 1;
cin >> num;
while (last_ptr <= num) {
if (sum < num) {
last_ptr++;
sum += last_ptr;
}
else if (sum > num)
{
sum -= first_ptr;
first_ptr++;
}
else {
counter++;
last_ptr++;
sum += last_ptr;
}
}
cout << counter << "\n";
return 0;
}
추가적인 생각 및 아쉬운 점
일단 이런 투포인터 방식문제라는 것을 알았었고 내 머리로 풀고 싶어서 개념을 보지 않고 풀어보다가 투포인터에 대해서 살짝만 찾아서 부분합으로 풀어봤다가 메모리 초과로 틀렸었다. 그리고 마지막에 내가 다시 생각해서 개선한 코드가 사실 시간 복잡도가 얼마나 될지 모르고 그냥 $O(N^2), O(N\log N)$ 보다는 작지 않을까? 이런 생각으로만 풀어서 이 코드가 정확하게 얼마의 시간복잡도가 있는지 아직까지는 정확하게 모르겠다. 알고리즘을 듣고 있는데 조만간 시간복잡도를 계산해 봐야겠다.
댓글