2003. 수들의 합2_반례

·2022년 9월 5일
0

백준 알고리즘

목록 보기
108/270
post-thumbnail

일반적인 생각으로 풀면 250902

  • 52퍼센트에서 틀리는데, 왜냐하면 마지막 값이 m인 경우 처리해야 한다.

  • 마지막 인덱스에 대한 처리를 해야 한다.
    : 마지막 값을 누적하게 되면, 자동적으로 while문 조건에 걸려서
    처리되지 않게 된다.

  • 빈깡통 하나 추가하면 된다.

문제 해결방법에 대해서

  • 이럴 때는 반례에 대해서 생각해야 한다.
    입력 예제에서는 가장 마지막값이 m인 경우가 없다.
    마지막값이 m일수도 있겠지? 를 생각하면 해결할 수 있는 문제다.

결론

: 일반적인 배열 인덱스까지 진행하면 답이 나오지 않으므로,
인덱스 하나 더 늘리는데, 누적해도 문제가 없는 초기화를 모두 0으로 처리하자.

일반적인 생각으로 접근하면

  • 이렇게 작성하게 된다.
vector<int>v(n);

for (int i = 0; i < n; ++i)
{
	cin >> v[i];
}

// 고정하는 용도로만 사용할까?? 
int sstart = 0;
int eend = 0;

int sum = 0;
int cnt = 0;


while (  eend < n)
{	
	if (sum >= m)
	{
		if(sum == m)
			++cnt;

		sum -= v[sstart];
		sstart++;
		
	}		
	else if (sum < m)
	{
		
		sum += v[eend];
		eend++;
		
	}

}

-> 이렇게 작성하게 되면, eend < n 이 되기 때문에 1번 예제는 옳지 못한다.

  • 트릭을 사용하자.
    위의 코드는 아무리 생각해도 맞는 결과이기 때문에 차라리
    n 인덱스 값을 하나 더 추가하고, 0으로 만들자.
    그리고 조건을 <= 으로 해서
vector<int>v(n + 1);

for (int i = 0; i < n; ++i)
{
	cin >> v[i];
}

// 고정하는 용도로만 사용할까?? 
int sstart = 0;
int eend = 0;

int sum = 0;
int cnt = 0;


while (  eend <= n)
{	
	if (sum >= m)
	{
		if(sum == m)
			++cnt;

		sum -= v[sstart];
		sstart++;
		
	}		
	else if (sum < m)
	{
		
		sum += v[eend];
		eend++;
		
	}

}
profile
🔥🔥🔥

0개의 댓글