[BOJ / C++] 2003번 수들의 합 2
이번 문제는 for문을 이중으로 사용하여 풀었다.
- 연속된 값들을 계속 더하여 cnt가 m과 같아지면 result를 증가시킨다.
- cnt가 m보다 작다면 계속 반복한다.
Code
#include <iostream>
#define MAX 10001
using namespace std;
int n, m;
int A[MAX];
int cnt=0;
int result=0;
void Input(){
cin>>n>>m;
for(int i=0; i<n; i++){
cin>>A[i];
}
}
void Solution(){
for(int i=0; i<n; i++){
cnt=A[i];
if(A[i]==m){
result++;
}
for(int j=i+1; j<n; j++){
cnt+=A[j];
if(cnt==m){
result++;
}
else if(cnt<m){
continue;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution();
cout<<result<<endl;
return 0;
}
#include <iostream>
#define MAX 10001
using namespace std;
int n, m;
int A[MAX];
int cnt=0;
int result=0;
void Input(){
cin>>n>>m;
for(int i=0; i<n; i++){
cin>>A[i];
}
}
void Solution(){
for(int i=0; i<n; i++){
cnt=A[i];
if(A[i]==m){
result++;
}
for(int j=i+1; j<n; j++){
cnt+=A[j];
if(cnt==m){
result++;
}
else if(cnt<m){
continue;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution();
cout<<result<<endl;
return 0;
}
문제는 풀었지만 알고리즘 분류에 두 포인터로 명시되어 있었고 두 포인터로 푸는 법도 찾아보았다.
- low, high로 두 포인터를 설정해준다.
- cnt의 크기에 따라서 low, high의 위치를 조정한다.
- high가 n보다 커지면 while문을 끝낸다.
- while문 안에서는 cnt가 m보다 커지면 low가 가리키는 값을 빼고, high가 가리키는 값을 더한다.
- 쉽게 말하면 low로 빼고, high로 더한다.
Code
#include <iostream>
#define MAX 10001
using namespace std;
int n, m;
int A[MAX];
int low=0, high=0;
int cnt=0;
int result=0;
void Input(){
cin>>n>>m;
for(int i=0; i<n; i++){
cin>>A[i];
}
}
void Solution(){
while(1){
if(cnt>=m)
cnt-=A[low++];
else if(high==n)
break;
else
cnt+=A[high++];
if(cnt==m)
result++;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution();
cout<<result<<endl;
return 0;
}
이러한 문제는 두 포인터 알고리즘을 사용하면 시간이 단축된다는 사실을 알 수 있었다.
Author And Source
이 문제에 관하여([BOJ / C++] 2003번 수들의 합 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-C-2003번-수들의-합-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)