rlagjqm2   2년 전

결론부터 말하자면 27, 29번째 줄이 이해가 안됩니다.

제가 이해한바는 누적합 배열이 sum 배열 이라고 하면

구간합은 sum[i] - sum[j-1] = k 가 되고,

우리는 sum[i] 와 k를 알고 있기 때문에 결국 sum[i] - k = sum[j-1] 이라는 식을 만들수 있고,

저 말은 map에서 구간합인 sum[j-1]의 개수를 찾아내 정답에 더하면 된다고 이해했습니다.

여기서 궁금한게 있습니다.

1. 27번째 줄에서 처음에 map에 구간합이 0인걸 넣어주는 이유는 무엇인가요?

2. 29번째 줄에 정답을 더해가는 과정에서 중복이 일어날 수 있는거 아닌가요?

  • 2번의 경우 예를들면 map에 key:1 , value:1 이 먼저 존재하고 있었다면 sum[i] - k 가 1이 나오게 될때 answer에 1을 더해줍니다.
    그리고 30번째 줄에 의해 map에선 key:1 , value:2 가 되고 나중에 또다시 sum[i] - k 가 1이 나오면 answer에 2를 더해주게 되는데 사실은 1을 더해야 하는거 아닌가요?

알려주세요..... 젭ㄹ...

fccva   2년 전

1. 만일 sum[i]가 k라면(즉 sum[j-1]을 빼지 않고도 찾았다면)

합이 k인 구간을 하나[0, i] 찾았으니 answer에 1을 더해줘야하는데, 그 부분을 처리해주기 위해 map.put(0, 1)을 해준겁니다.

그러면 29번째 줄에서 answer를 1 늘려줍니다.

만일 map.put(0, 1)을 넣지 않고 싶다면, for 문 안에서

if (sum[i] == k) answer++; 를 한 줄 추가해주면 됩니다. (map.put(0, 1)이 해주는 역할과 똑같습니다.)

2.

  • 2번의 경우 예를들면 map에 key:1 , value:1 이 먼저 존재하고 있었다면 sum[i] - k 가 1이 나오게 될때 answer에 1을 더해줍니다.
    그리고 30번째 줄에 의해 map에선 key:1 , value:2 가 되고 나중에 또다시 sum[i] - k 가 1이 나오면 answer에 2를 더해주게 되는데 사실은 1을 더해야 하는거 아닌가요?

map에 이미 key:1, value:1이 존재하고 있다면 (sum[x] == 1인 x가 1개 존재(x < i))

sum[i] - k = 1일 때 answer에 1을 더해줍니다.(맞습니다. [x+1, i]까지의 부분합이 k라는 의미이고 이러한 x의 개수가 1개니까 1을 더해줍니다.)

30번째 줄에 의해서 key:1, value:2가 되고 (아닙니다. key:1 이 아니라 key: k+1의 value가 늘어나죠)

나중에 또 다시 sum[i] - k = 1이 나온다면 (sum[x] = 1인 모든 x에 대해서 [x+1, i]의 부분합이 k입니다. 따라서 sum[x]=1을 만족하는 x의 개수를 answer에 더해주는 것이 맞습니다.)

30번째 줄은 sum[i]의 개수를 올려주는 것입니다. sum[i]-k의 개수를 올려주는 것이 아니구요.

rlagjqm2   2년 전

덕분에 어느 정도 이해가 됐습니다.

2번같은 경우 아예 잘못 생각하고 있었군요.. 감사합니다!

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