-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
질문있습니다.
21.07.20 15:33 작성 조회수 144
0
41번 연속된 자연수의 합(단순 수리)의 코드를
i를 1부터 증가시켜서 연속되는 자연수의 합이 주어진 수를 만족하는 경우에 해당 수들을 출력하도록 코드를 짜보았는데, 이렇게 해도 되는건가요?
혹시 틀린 부분이 있다면 알려주시면 감사하겠습니다.
#include<stdio.h>
using namespace std;
int main(){
//freopen("input.txt", "rt", stdin);
int n, i, k, sum, tmp, cnt=0;
scanf("%d", &n);
for(i=1; i<n; i++){
sum=0;
tmp=i;
while(sum<n){
sum+=tmp;
tmp++;
}
if(sum==n){
for(k=i; k<tmp-1; k++){
printf("%d + ", k);
}
printf("%d = %d\n", k, sum);
cnt++;
}
}
printf("%d\n", cnt);
return 0;
}
답변을 작성해보세요.
1
김태원
지식공유자2021.07.22
안녕하세요^^
네. 잘하신 코드입니다. 위에 코드는 시간복잡도가 O(n^2)입니다. 영상에서 한 방법도 알아두셔야 하고, 아래 코드처럼 tow pointers 알고리즘으로 O(n)으로 할 수 도 있습니다. 아래 코드 한 번 분석해 보세요.
아래 코드에서 for 문 안쪽의 while문의 프로그램 전체 총 반복횟수가 n입니다.
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
freopen("input.txt", "rt", stdin);
int n;
cin>>n;
vector<int> ch(n/2+1);
for(int i=0; i<=n/2+1; i++) ch[i]=i+1;
int lt=0, sum=0, cnt=0; //lt => left, rt => right
for(int rt=0; rt<=n/2+1; rt++){
sum+=ch[rt];
if(sum==n) {
cout<<ch[lt]<<"~"<<ch[rt]<<"="<<n<<endl;
cnt++;
}
while(sum>n){
sum-=ch[lt++];
if(sum==n) {
cout<<ch[lt]<<"~"<<ch[rt]<<"="<<n<<endl;
cnt++;
}
}
}
cout<<cnt<<endl;
return 0;
}
최정은
질문자2021.08.05
넵 안녕하세요! 답변 정말 감사합니다.
답변 해주신 코드 관련 질문이 있습니다.
1. 왜 배열의 크기를 vector<int> ch(n/2+1); 이렇게 잡은 것인가요? 이유가 있을텐데 궁금합니다.
2. 첫번째 for문에서 for(int i=0; i<=n/2+1; i++) ch[i]=i+1; i가 왜 n/2+1까지 인것인가요? n/2까지 해도 배열에 저장될때는 +1되어서 저장되니깐 n/2라고 생각했는데 왜 그런지 궁금합니다. 그리고 추가로 n/2까지라고 하면 두번째 for문의 경우도 rt가 n/2까지로 변경하면 되는 것인지도 궁금합니다.
답변 1