[구름] 어부의 고기잡이 C++

https://level.goorm.io/exam/49096/%EC%96%B4%EB%B6%80%EC%9D%98-%EA%B3%A0%EA%B8%B0%EC%9E%A1%EC%9D%B4/quiz/1

구름LEVEL

 

 

풀이

 

투포인터 알고리즘

start와 end 변수를 각각 시작, 끝 포인터로 활용

 

1. input[start] 부터 input[end]  까지 더한 값 sum이 m보다 작으면 end+ 1

2. m보다 크면 start + 1

3. m과 같으면 answer + 1 (경우의 수 카운트)

4. m보다 작으면서 end 포인터가 input의 길이를 벗어날 경우 >> 더이상 정답이 나올 수 없는 경우

 

 

 

	int main() {

		int n;
		int m;
		cin >> n >> m;

		vector<int> input;

		// input vector에 입력 값 저장
		for (int i = 0; i < n; i++) {

			int temp;
			cin >> temp;
			input.push_back(temp);
		}

		int start=0;		// 왼쪽 포인터
		int end=0;			// 오른쪽 포인터
		int answer = 0;		// 정답 카운트

		// end가 input 의 범위 안일 경우 반복
		while (end<n) {

			// start ~ end 의 합
			int sum=0;
			for (int i = start; i <= end; i++)
				sum += input[i];
			
			// sum == m 일 경우 정답 카운트 + 1
			if (sum == m) {
				answer++;
                
                // start 포인터 1 증가
				start += 1;
			}

			// sum < m 일 경우
			else if (sum < m)
            	// 다른 수를 더해서 m을 만들어야 하므로 end 포인터 증가
				end += 1;
                
            // sum > m 일 경우
			else if (sum > m)
            	// 수를 작게 만들어야 하므로 start 포인터 증가
				start += 1;
		}
		cout << answer << endl;
	}