mic1021   7년 전

시간초과 안나게끔 코드를 짜봤습니다..

map[j]=1번부터 i번 숫자 중에서 부분집합의 합이 j인 집합의 총 갯수

mic1021   7년 전

앗 !! cnt 가 nC2개니까 long long써야 되군요 ㅋㅋㅋㅋㅋ

temp   7년 전

ma[0]=1;

여기서 ma[0] 이 1인 이유가 부분합중 어떠한 원소도 고르지 않을 경우를 뜻하는게 맞나요?


if(ma[num[i]-k]>0) {
            cnt+=ma[num[i]-k];
        }
        ma[num[i]]++;

이부분에 대한 설명도 자세히 부탁드려도 될까요?

mic1021   7년 전

temp  

map[0]을 1로 초기화한 이유는 num[i]에서 num[j]를 빼지 않고 num[i]자체만으로

도 k가 되는 경우를 고려하기 위함입니다.

코드 구조를 보시면 1번 숫자부터 마지막 숫자까지 차례대로 도는 for문이 있습니다.

12번째 줄은 1번부터 지금 순서의 번호까지의 연속합을 num배열에 저장하기 위함입니다.

13-15번째 줄의 원리는 현재 번호가 i번째 일때 num[i]-num[j]=k를 만족시키는 j가 몇 개 존재하는 

지 알아내는 것입니다.(1<=j<i) 

16번째 줄에 현재 구한 부분합의 map성분값을 1추가 시키는데 이유는 나중가서 num[j]로 현재구한 

부분합이 쓰일 수 있기 때문입니다.

mic1021   7년 전

엇! 제가 설명을 이상하게 했네요.. 수정할게요

13-15번째 줄의 원리는 현재 번호가 i번째 일때 num[i]-num[j]=k를 만족시키는 j가 몇 개 존재하는 

지 알아내는 것입니다.(1<=j<i)

--> 13-15번째 줄의 원리는 현재 번호가 i번째 일 때 num[i] - ?? = k를 만족시키는 ??가 있다. 부분합

이 ??가 되는 총 경우의 수를 알아내는 것입니다. 따라서 map정의를 ma[i]=부분합이 i가 되는 부분합

의 총 경우의 수 로 둔것이지요

temp   7년 전

답변 감사합니다. 거의 이해가 되었습니다.

아직 제가 의문을 품는게 하나 있는데요.

예제에서 

2 -2 2 -2 일때 0이되는경우는

1번 2번을 합한경우

3번 4번을 합한경우

2번 3번을 합한경우

1~4번 전부 합한경우

해서 4가지라고 생각했습니다. 맞나요?


현재 구한 배열은 1번인덱스부터 n번인덱스까지 계속 합을 늘려가는 식인데요.

어째서 저기서 3번 4번의 합이나 2번 3번의합을 구할수있는걸까요?

그니까 num[i]라는 애는 1번인덱스부터 i번째 인덱스까지의 합인데 이녀석들을 가지고 k를 이용하여 값을 구한다고 해도 저런 중간값들은 찾을수 없지 않나요?

mic1021   7년 전

num배열은 1번부터 계속해서 더한 부분합들을 저장하고 있는 배열이지요.

위의 예시인 4 0 2 -2 2 -2 를 생각해봅시다. num[1]=2 num[2]=0 num[3]=2 num[4]=0 입니다.

이 정보만으로 알 수 있는 건 부분합이 2가 되는 경우는 1~1과 1~3 두가지 경우이고

부분합이 0이 되는 경우는 1~2 1~4 두가지 경우다 라는 것입니다.

질문하신 대로 2~3도 부분합이 0이 되는데 이건 어떻게 답에 포함시킬것인가? 하는 문제는

13~15번째 줄에서 해결이 됩니다. 

앞서 for문에 대해 보충설명 드리자면 for문을 도는 목적은 num[i]가 포함된 부분합을 고려했을 때 부

분합이 k가 되는 모든 경우의 수를 구하는 겁니다.

i가 3일때를 보면 ma[num[3]-k]>0 이면 정답에 ma[num[3]-k]를 더합니다.

k = num[3] - (num[3] - k) 이기 때문에 ma[num[3]-k] 가 ma[k]에 포함됩니다.

부분합이 num[3]-k인 모든 경우의 수를 구할 수 있다면 k가 나오는 총 경우의 수도 구할 수 있다는 것

이지요. 

예를 들어, 입력으로 4 0 2 -2 2 -2가 주어졌을 때, 1~4 그 자체로도 0이 됩니다.(=1~4 - (1~4)) 하지만

1~4 - (1~2) = 3~4 또는 1~4 - (2~3) = 1&4 또는 1~4 - (3~4) = 1~2 와 같은 경우에도 0이 될 수 있습

니다. 괄호안 범위들의 공통점이 무엇인가요? 그 범위안의 부분합이 0, 즉 k라는 사실입니다.

즉, ma[k]만큼 존재하는 경우의 수 안에는 num[i] (1<=i<=4) 를 포함시켰을 때 부분합이 k인 총 경우

의 수가 포함됨을 알 수가 있습니다.

num[3]=2이므로 ma[2-0], 즉 부분합이 2가 되는 모든 경우의 수들만 찾는다면 num[3]을 포함

면서 부분합이 k인 경우의 수를 구할 수 있게 되겠지요. i=3일때 ma[2]=1입니다. i=1일때 16번째줄에

의해서 ma[2]++되었기 때문이지요. 따라서 ma[2]=1 은 곧 1~1케이스를 말하는

겁니다. 1~3 - (1~1) = 2~3 입니다. 따라서 i=3일 때 cnt에 ma[num[3]-k]를 더해주는 것은 곧 2~3범

위를 포함시켜준다는 의미입니다.


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