[C++] 백준1292번 쉽게 푸는 문제

1. 문제이해

https://www.acmicpc.net/problem/1292

1292번: 쉽게 푸는 문제

 

1을 한번, 2를 두번, 3을 세번, 이런식으로 1 2 2 3 3 3 4 4 4 4 ... 이루어진 순열이 있다.

어느 일정한 구간이 주어졌을 때, 그 구간의 합을 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 ...

위와 같이 자연수 n 이 n 번 나타나는 형태의 수열에서, 주어진 구간의 합을 구하는 문제이다.

주어진 범위가 비교적 크지 않기 때문에, (1 ≤ A ≤ B ≤ 1,000)

수열을 만든 후에 해당 범위 내의 합을 구해주어도 무관한 문제이다.

 

예제 입력 1을 보자.

주어진 범위가 3 ~ 7 까지 이므로, 최대 7번째 수열까지만 확인하면 된다.

따라서, 수열의 크기가 7이 될때까지 위와 같은 규칙을 적용하여 수열을 만들고,

만들어진 수열에서 범위 내의 합을 구해주면 된다.

 

 

 

3. 소스코드

#include <iostream>
#include <vector>
using namespace std;

vector <int> v;

// 크기가 n 이면서, 규칙을 만족하는 수열을 만드는 함수
void make_arr(int n) {

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			// 사이즈가 n 이 되면 종료
			if (v.size() == n) {
				break;
			}
			v.push_back(i);
		}
	}

}

int main() {
	int A, B;
	int sum = 0;

	cin >> A >> B;

	make_arr(B);
	// 범위 내의 합을 구해준다. (배열값이므로 -1)
	for (int i = A - 1; i <= B - 1; i++) {
		sum += v[i];
	}

	cout << sum;

	return 0;
}

make_arr 함수는 문제의 규칙을 만족하면서 크기가 n인 수열을 만들어준다.

메인 함수에서 합을 구해야하는 범위인 A, B를 입력받은 뒤,

make_arr 함수를 통해 크기가 B인 수열을 만들어준다.

(입력받은 최대 범위까지만 숫자를 알면 되기때문에 B를 넣어준다.

1000을 넣어도 무방하지만, 다양한 경우를 고려했을때 해당 방법이 더 효율적이다.)

이후, 만들어진 수열에 대해 A부터 B까지의 범위에 대한 합을 구하고 출력했다. (배열값이므로 -1 필요)

 

주석없는 코드는 왼쪽 아래 더보기를 참고바랍니다.😊

<주석 없는 코드>

#include <iostream>
#include <vector>
using namespace std;

vector <int> v;

void make_arr(int n) {

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			if (v.size() == n) {
				break;
			}
			v.push_back(i);
		}
	}

}

int main() {
	int A, B;
	int sum = 0;

	cin >> A >> B;

	make_arr(B);
	for (int i = A - 1; i <= B - 1; i++) {
		sum += v[i];
	}

	cout << sum;

	return 0;
}

 

 

---

문제에 대한 지적이나 질문은 언제나 감사하게 받고있습니다.😊