앗 !! cnt 가 nC2개니까 long long써야 되군요 ㅋㅋㅋㅋㅋ
2015번 - 수들의 합 4
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]로 현재구한
부분합이 쓰일 수 있기 때문입니다.
답변 감사합니다. 거의 이해가 되었습니다.
아직 제가 의문을 품는게 하나 있는데요.
예제에서
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를 이용하여 값을 구한다고 해도 저런 중간값들은 찾을수 없지 않나요?
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범
위를 포함시켜준다는 의미입니다.
댓글을 작성하려면 로그인해야 합니다.
mic1021 7년 전
시간초과 안나게끔 코드를 짜봤습니다..
map[j]=1번부터 i번 숫자 중에서 부분집합의 합이 j인 집합의 총 갯수