• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

이 방법은 시간복잡도가 On2 정도일까요?

22.05.09 17:38 작성 조회수 267

0

int main()
{
	freopen("input.txt", "rt", stdin);

	int n;

	scanf("%d", &n);

	std::vector<int> list;
	int sum = 0;
	int count = 0;
	for (int i = (n/2) + 1; i > 0; i--)
	{
		int temp = i;
		sum = 0;
		list.clear();
		while (true)
		{
			sum += temp;
			list.push_back(temp);
			temp--;

			if (sum == n)
			{
				for (int k = list.size() - 1; k > 0; k--)
				{
					printf("%d + ", list[k]);
				}
				printf("%d = %d\n", list[0], sum);
				count++;
				break;
			}
			else if (sum > n)
			{
				break;
			}
		}
	}

	printf("%d", count);

	return 0;
}

 

반복문이 3번 등장해서 좋지 못하다고 생각듭니다.

시간복잡도가 On2 이상 일까요?

답변 1

답변을 작성해보세요.

1

안녕하세요^^

네. 좀 개선을 해야 할 것 같습니다.