seungwonoh57   2년 전

안녕하세요.

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

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

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

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

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

gaelim   2년 전

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

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   2년 전

아 정정, 처음 5에서부터 탈출하게 되겠지요 

gaelim   2년 전

#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);
}


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

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