백준/ Silver1 문제 , 백준 파이썬 11660 , 구간 합

백준/ Silver1 문제 , 백준 파이썬 11660 , 구간 합

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
그냥 처음에 중첩 for 문을 사용하여 더하니 시간초과가 났다.
이렇게 구간합을 구해놓고 필요한부분만 더하고 빼주면 속도가 빨라진다.
python3 에서는 여전히 시간 초과가 나는 코드지만, pypy3 는 통과했다.

 

 

 

 

 

<문제 출처>

 

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

------------------------------------------------------------------------------------------------------------------------------

 

 

처음 작성한 코드이다. 이렇게 작성하면 시간초과가 난다.

 

 

 

https://claude-u.tistory.com/427

#374 백준 파이썬 [11660] 구간 합 구하기 5

 

이 블로그에서 솔루션을 얻었다.

 

바로 구간 합을 이용하는 것인데,

 

 

문제에서 주는 예시1 로 설명해 보겠다.

 

 

 

예시1

예시1 에서 주어진 행렬이다. 

 

구하려는 부분은 (2,2) ~ (3,4) 에 해당하는 부분으로 2행 3부터 3행 6까지의 합이다.

 

이 예시는 쉽게 계산이 되지만, 원리를 알아보자.

 

 

 

 

 

이렇게 바꿔 주었는데 1열은 똑같고, 2열부터는 값을 차근차근 더해나간 값들이다.

 

2열 3 5 7 9 는 원래 2열이였던 2 3 4 5 에다가 1열 1 2 3 4를 더해준 것이다.

 

2+1=3

3+2=5

4+3=7

5+4=9 

 

를 해준 값이다.

 

그러면 자연스레 3열은 원래 3열  3 4 5 6에다가 위에서 새로 만든 2열 3 5 7 9 를 더한 값이겠다.

 

 

3+3=6

5+4=9

7+5=12

9+6=15

 

이 값이 새로운 3열을 차지 하게된다.

 

이런식으로 끝열까지 쭉 더해서 새 행렬을 만들어주면 된다.

 

 

 

 

그 후 구하려는 구간을 보면 이 네모칸 안에 있는 구간들이다.

 

하지만, 여기서 중점으로 봐야할 곳은 맨 오른쪽 구간이다. 

 

이 오른쪽에 써져있는 값들이 그 행에서 열까지 다 더한 값이고

 

구하려는 행의 값 들을 다 더한 값은 저 14에 해당하는 부분에서 구간에 속하지 않는 2를 빼주면된다.

 

즉, 14-2=12 가 구하려는 범위 내의 2행의 구간 값이다.

 

3행은 그럼 당연히 18-3=15 가 구하려는 범위내의 3행의 구간 값일 것이다.

 

 

이 예시는 2행과 3행까지만 필요하므로, 각 행에서 나온 값들을 더한 12+15=27 이 값이 최종 답이다.

 

 

이런 원리를 적용하여 문제를 풀어나가면 된다.

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

정답