문제 URL : https://www.acmicpc.net/problem/1024
1024번: 수열의 합
첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.
www.acmicpc.net
문제 접근법 :
일반항을 구해보면 2가지로 해석을 할수있습니다.
로 구해질수 있습니다. 오른쪽 La + L(L-1)/2 를보면 두가지의 변수 a와 L의 값으로 n이 되는값을 찾으면됩니다.
소스코드 1번:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, l;
void input() {
cin >> n >> l;
}
void solve() {
for (ll L = l; L <= 100; L++) {
for (ll a = 0;; a++) {
if (n == (L * a + (L * (L - 1)) / 2)) {
for (ll i = 0; i < L; i++)
cout << a + i << " ";
return;
}
else if (n < (L * a + (L * (L - 1)) / 2))
break;
}
}
cout << -1 << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
시간을 보면 매우 느리다는것을 알수있습니다. 좀더 줄일 수있는 방법을 생각해보면 일반항을 좀더 다르게 해석해야합니다.
마지막 일반항에서 L(L-1)/2를 이항시키면 위와같은 식이 성립됩니다.
그렇다면 L의 범위는 입력값<=L<=100까지 입니다.
그리고 왼쪽의 식을 T라고 가정하면
T=La라는 식이 나오고 T자체가 L의 약수임을 알수있니다. 즉 약수일때 a의 값을 쉽게 알수있기때문에 L하나만 변수로 잡을수 있습니다.
소스코드 2번 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, l;
void input() {
cin >> n >> l;
}
ll Summ(ll t) {
return (t * (t - 1)) / 2L;
}
void solve() {
for (ll L = l; L <= 100; L++) {
ll sum = n - Summ(L);
if (sum % L == 0&&sum/L>=0) {
for (ll i = sum / L; i < L + (sum / L); i++) {
cout << i << " ";
}
return;
}
}
cout << -1 << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 21610 마법사 상어와 비바라기 (0) | 2021.08.19 |
|---|---|
| 백준 13900 순서쌍의 곱의 합 (0) | 2021.08.16 |
| 백준 1043 거짓말 (0) | 2021.08.15 |
| 백준 20058 마법사 상어와 파이어스톰 (0) | 2021.08.13 |
| 백준 19238 스타트 택시 (0) | 2021.08.11 |
