[백준][C++] 2440번 별찍기-3

별찍기-3

문제 링크

별찍기-3

분석

입력으로 주어지는 정수 N으로 다음과 같이 별을 출력해야 합니다.

1 번째 줄에는 *가 N개
2 번째 줄에는 *가 N-1개
3 번째 줄에는 *가 N-2개
N 번째 줄에는 *가 1개

즉, 첫 줄에서 가장 많은 별을 출력하고, 줄이 내려갈수록 별의 개수가 하나씩 감소하는 내림차순 형태로 출력하는 문제입니다.

해당 문제는 별찍기-1번의 문제와 반대로 별의 개수가 증가하지 않고 감소하는 형태입니다.

대표적으로 이중 반복문으로 풀이할 수 있습니다.

풀이

#include <iostream>

using namespace std;

int main()
{
	int N;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N - i; j++)
		{
			cout << "*";
		}
		cout << endl;
	}
}

성능 요약

시간 복잡도는 $O(n^2)$입니다.

-바깥 반복문 $O(n)$ -안쪽 반복문 $O(n)$ -$O(n) \times O(n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

메모리: 2020 KB

시간: 4 ms