반응형
이 문제의 시간 제한은 2초, N의 최댓값은 100000000이므로 제한 시간을 맞추기 위해서 투 포인트를 사용해야 합니다.
시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현해보자
풀이 방식을 두 가지 정도 생각해보았습니다.
첫번째 풀이 방식
1. 시작인덱스부터 종료 인덱스까지 탐색하면서 합이 N이 될 때를 카운트한다.
2. 만약 sum하고 N 값이 같을 때는 종료 인덱스를 더 큰 쪽으로 한 칸 옆으로 보내고, sum값을 바뀐 종료 인덱스를 더 한 값으로 초기화한다. 그리고 count도 시켜준다.
3. 만약 sum보다 N이 작을 때는 종료 인덱스를 더 큰 쪽으로 한 칸 옆으로 보내고, sum값을 바뀐 종료 인덱스를 더 한 값으로 초기화한다.
4. 만약 sum이 N보다 작다면 sum에서 시작인덱스 값을 빼주고, 시작인덱스를 더 큰 쪽으로 한 칸 옆으로 보낸다.
#include <iostream>
#include<string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin.tie(NULL);
int num;
cin >> num;
int sum = 0;
int start index=1;
int end_index=1;
int sum=1
int count = 0;
while(end_index !=N){
if(sum==N){
count++;
end_index++;
sum+=end_index;
}
else if(sum>N){
sum+=start_index;
start_index++;
}
else{
end_index++;
sum+=end_index;
}
}
cout << count+1;
}
두 번째 방식
1. for문을 활용해서 1부터 N 전까지 반복시킨다.
2. 만약 N의 값이 sum보다 작아지면 sum을 0으로 초기화 시킨다.
3. 만약 N의 값이 sum 값하고 같다면 count를 하고 sum을 0으로 초기화시킨다.
4. 만약 N값이 sum보다 크다면 그 반복문의 해당하는 숫자를 더해준다.
#include <iostream>
#include<string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin.tie(NULL);
int num;
cin >> num;
int sum = 0;
int count = 0;
for (int i = 1;i < num;i++) {
for(int j=i;j<num;j++)
if (num < sum) {
sum = 0;
break;
}
else if (num == sum) {
count++;
sum = 0;
break;
}
else {
sum += j;
}
}
cout << count+1;
}
반응형
'코딩공부 > 코딩테스트 공부 일기장' 카테고리의 다른 글
11286번 절댓값 힙(우선순위큐와 abs) (0) | 2024.04.04 |
---|---|
29723번 브실이의 입시전략 (0) | 2024.04.03 |
백준 1874번 스택수열 (0) | 2024.04.02 |
3월 23일 스택과 큐 공부 (0) | 2024.03.25 |
1940번 난이도:실버 4 (주몽의 명령) (2) | 2024.03.07 |
댓글