[2] 숫자의 표현(일반식 도출하기)

문제 설명
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항
n은 10,000 이하의 자연수 입니다.

---

★ 이중 포문의 문제가 아니다. 

★ 등차수열을 활용해 일반식을 도출해서 풀어야 하는 문제이다.

- 처음엔 이중포문으로 풀었다.

#include <string>
#include <vector>

using namespace std;

int solution(int n)
{
	int answer = 0;

	// n 횟수 만큼 반복
	// 1부터 더해서 n과 동일해지면 되면 카운트 +1
	// n보다 커지면 다음 2부터 시작
	for (int i = 1; i <= n / 2; i++)
	{
		int val = 0;
		for (int j = i; j <= n; j++)
		{
			val += j;
			if (val == n)
				answer++;
		}
	}

	return ++answer;
}

하지만 O^2의 시간 복잡도로 시간초과가 남

 

★ 식을 고민하다 결국 다른 블로그를 찾아보며 힌트를 얻었다.

아래는 유도한 방법

- 더해서 나오는 목표값: n

- 연속된 덧셈의 시작값: a

- 더하는 개수: k

1. 식부터 유도하자

ㄴ 일단 1부터 10까지 더하면 55, 이는 (1 + 10) 값을 1부터 10까지의 개수(10)에서 2를 나눈 값을 곱한 결과이다.

ㄴ 1부터하니 뭔가 헷갈려서 3부터 10으로 친다면 개수는 (10 - 3 +1)이므로 계산하면 8/2*(10+3) = 52

2. 일반식으로

ㄴ n = a + (a+1) + (a+2) + ... + (a+k-2) + (a+k-1) // k를 k-1까지 해야 총 개수가 k 개이다.

ㄴ 이걸 일반식으로

ㄴ 개수는 k 개 이므로, k/2*(a+(a+k-1) = n 이라는 식이 나온다.

이때 조건을 따지면 n과, k, a 모두 자연수이다.

a를 좌항으로 보내면

=> 2a + k - 1 = 2n/k

=> 2a = 2n/k - (k + 1)

=> a = n/k - (k + 1)/2

가 된다.

3. 조건 따지기

ㄴ a는 자연수 이므로, 우항의 n/k와 (k+1)/2 가 모두 정수가 되려면, n은k로 나누어떨어지고, k는 홀수여야 한다.

ㄴ (n % k == 0 && k % 2 == 1) 

#include <string>
#include <vector>

using namespace std;

int solution(int n)
{
	int answer = 0;

	for (int i = 1; i <= n; i++)
		if (n % i == 0 && i % 2 == 1)
			answer++;
	
    return answer;
}

 

★ 덧 붙이기

ㄴ 가끔은 문제 접근 자체를 다시해야한다.

답을 구하는 것이 아니라, 해당 답이 나오기 위해 필요한 조건을 활용해서 답을 구하는 방식을 고민해보자

그러기 위해서는 일반식을 도출하는게 좋다.

 

ㄴ 이전 모회사 코테에서 2중포문으로 풀리지만 시간 초과때문에 실패했던 문제가 있었다.

그때도 이런 유형이지 않았을까 싶다.

그땐 도저히 이중 포문 말고는 답을 모르겠어서 못풀었었다.