글 읽기 - i가 j보다 같거나 작을 때까지만 while문을 돌릴 때 문제 발생

seungwonoh57 6년 전 0

안녕하세요.

문제가 i번째에서 j번째 수까지의 합을 구하는 문제라

while문 안에 조건이 i가 j보다 커지는 조건을 중급 알고리즘 2 강의에서는 넣어져있는데

실제로 그렇게 하면 만약 배열 값 중 하나라도 M보다 큰 값이 있을 시, i가 j보다 커지면서 뒤에 경우의 수들을 다 확인하지도 못하고 끝나버리는 경우가 생깁니다.

오히려 i <= j 조건을 없애야 정확한 답이 나온다고 생각이 드는데요.

혹시 강의 들으신 분 중에서 그 i <= j 조건이 왜 있는지 아시는 분, 또는 안 들으신 분 중에서도 이유를 아시는 분 답변 부탁드립니다.

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char** argv)
{
	
	int N, M;
	int i = 1, j = 1;
	int sum, ans = 0;
	vector <int> a;
	
	scanf("%d %d", &N, &M);
	
	a.resize(N+1);
	
	for(int i = 1; i <= N; i++){
		cin >> a[i];
	}
	
	sum = a[1];
	
	while(i <= j && j <= N){ // i<=j 지워야 정답.
		if(sum < M){
			j++;
			sum += a[j];
		}
		else if(sum == M){
			ans += 1;
			j++;
			sum += a[j];
			
		}
		else{
			sum -= a[i];
			i++;
		}
	}
	
	cout << ans << endl;
	
	
	return 0;
	
}

gaelim 6년 전 0

지적하신바가 맞습니다. 문제조건에 따르면 테스트케이스가

5 2
5 2 10000 1 1

인 경우에는 경우의 수가 2가 나와야겠지요. 하지만 위의 코드에서 left <= right 조건이 들어간다면 10만이 너무 커서 left가 right를 오버하게되버리면서 반복문에서 탈출합니다. 저는 right가 입력 배열 크기를 넘어갈때까지 검색하도록 만들어보았습니다.

while 조건문에서 r<n 만 남겨두고 sum>obj 하위조건에서
else if (sum>obj) {
if (l==r) { r++; sum +=arr[r]}
else { sum-= arr[l]; l++}
}

로 하면 원하는 대로 나옵니다.

gaelim 6년 전 0

#include <stdio.h>

int main(){

int n, obj, ans=0;
int arr[10001];
scanf("%d %d", &n, &obj);

for(int i=0; i<n; i++) scanf("%d", &arr[i]);

int sum=arr[0];
int r=0, l=0;
while(r<n){
if(sum<obj) { r++; sum += arr[r];}
else if (sum > obj) {
if (l==r){r++; sum+=arr[r];}
else { sum-= arr[l]; l++;}
}
else if (sum==obj) {ans++;r++; sum+=arr[r];}
}

printf("%d\n", ans);
}

이런식의 코드도 잘 통과되네요 ^^;;

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

i가 j보다 같거나 작을 때까지만 while문을 돌릴 때 문제 발생

seungwonoh57 6년 전 0

gaelim 6년 전 0

gaelim 6년 전 0

gaelim 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말