lt 값이 바뀔 때마다 rt 를 lt+1로 초기화 하지 않아도 되... - 인프런

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

5. 수의 합

lt 값이 바뀔 때마다 rt 를 lt+1로 초기화 하지 않아도 되는 이유

작성

173

직관적으로 생각하면 lt 가 바뀔 때마다

rt = lt + 1 로 초기화해준 다음에

rt를 1씩 증가시키면서 확인해야할 것 같은데,

이전 lt 에 대한 rt 의 위치를 그대로 놔두고도

모든 경우를 빠짐없이 확인할 수 있다는 확신을 가질 수 있는 이유가 무엇인가요?

답변 1

지식공유자

안녕하세요^^

글로 증명하기가 좀 힘드네요.

그냥 반례가 존재하는지 스스로 확인해보는게 좋을 것 같습니다. 반례를 만들다 보면 감각적으로 확신이 들겁니다. 저도 그렇게 했습니다.

반례에 대해서도 설명해주시면 안되나요?

어떤 반례가 있는지 잘 모르겠어서요.. 이것저것 고민을 해봤는데

지식공유자

안녕하세요^^

수열의 모든 원소는 자연수라는 전제조건이 즉 음수가 없어야 하는 알고리즘입니다.

그리고 반례를 만들려고 해도 없다는 뜻입니다.

설명을 해보자면 lt가 증가한다는 것은 현재 lt에서 rt까지 연속된 합이 M이 되는지 이미 확인했다는 뜻이고 또 lt부터 rt까지의 합이 m보다 커졌다는 의미입니다. 그래서 lt를 증가시켜 lt부터 rt까지의 합을 작게 만들어 보는 것입니다.

그 결과 lt부터 rt까지의 합은 M보다 작거나, 크거나, 같은 이 세가지 경우가 나올 건데

만약 M보다 작으면 rt가 커지는 것이고

M보다 크면 lt가 증가하고,

M과 같다면 카운팅하는 것입니다.

위 원리가 의심가는 부분이 있으면 그 부분에 맞는 반례를 만들려고 노력해보라는 것입니다. 아마 만들어지지 않을 겁니다. 그렇게 원리를 이해하라는 뜻이었습니다.