[Do it 코테 자바편] 구간 합

설명

 

• 구간 합? a 배열에서 2~7번째 인덱스 값의 합을 구해란 것
• 처리하기 쉽게 a 배열을 가지고 합 배열 s를 만들어 보는 거다.
  • 합 배열? 즉 s[4]가 a[0] + a[1] + a[2] + a[3] +a[4]가 되도록 만드는 배열
  • 즉 s[4]는 a[0]부터 a[4]까지 합한 값이 된다.
  • 왜 필요? 그야 구간 합을 자주 물어보면 a 배열로 일일이 반복문 돌려서 하면 느리니까.
  • 합 배열 만드는 법? s[0]은 a[0]으로 초기화 후, 그 다음부턴 s[i] = s[i-1] + a[i]하면 됨. 즉 s[4] = s[3] + a[4]
• 합 배열로 구간 합 구하는 법? a[2] ~ a[5]의 합 => s[5] - s[1]
  • 왜? s[5]는 a0부터 a5까지의 합, s[1]은 a0부터 a1까지의 합 => 두 개를 빼면 a2+a3+a4+a5가 됨
  • 일반화하면, i에서 j까지의 구간 합은 s[j] - s[i-1]

 

관련 문제

[Java] 문제 003(백준 11659번)

 

[Java] 문제 004(백준 11660번)

 

[Java] 문제 005(백준 10986번)