백준 C++ 1292번 쉽게 푸는 문제 ( 누적합 )

 

오늘 점심에는 오랜만에

이삭토스트를 먹었다.

딥치즈 포테이토 베이컨을 먹었는데..

하나당 5800원이었다.

물가가 많이 올랐다는 것을 체감했다.

 

어제 내용을 복습하는데

분명.. 식에 이게 들어갔던 거 같은데.. 하면서 머리를 굴려서 풀었는데

이래도 되는가? 가 의문이다.

몇 번째 줄에 이게 들어갔지! 이거만 아니면 제씨가 괜찮다고는 했지만..ㅋㅋ

음...

ㅋㅋㅋㅋㅋ

복습도 어렵다.

---

 

동호는 내년에 초등학교에 입학한다면...

분명 지금 유치원생인데

도대체 이런 왕 어려운 문제를 어떻게 푼다는 건지..

나는 믿을 수가 없다..

 

쉽게 푸는 문제가 맞나 이게..

 

1 22 333 4444 55555...

 

3 ~ 7이어서

 

1 22 333 4444 55555...

 

15가 나온 건 알겠다.

이 패턴을 어떻게 설명해야 할지 잘 모르겠다.

 

아니 이렇게 어려운 문제가 도대체 왜 쉽게 푸는 문제 일까?

문제를 쉽게 푸는 방법을 이야기한 건가?

 

그.. 건 있다.

1+2 =3 세 번째..

그니까 3번째까진 2인 거고..

7은..

1+2+3 하면 6이니까

그다음 7이니.. 4를 더해줘야 한다는 사실..?

 

이걸 어떻게 계산해야 할까?

 

힌트를 결국 요청했다.

 

제씨는 a, b의 범위가 1000보다 작으니까

그냥 수열을 하나씩 다 배열에 넣자고 했다.

 

아차차..!!

나는 a,b의 범위라고 생각 못하고..

숫자가 1000까지 간다고 생각했다.

 

그래서 999개는 999개.. 1000개는 1000개까지 생각해서

절대 배열에 넣을 수 없는 크기라고 생각한 것..

 

바보..

문제는 진짜 제대로 읽어야 한다

 

그래서 준 힌트는

배열을 이중포문으로 채워 넣어주고,

왜냐면 1, 2, 2, 3, 3, 3.... 패턴을 해줘야 해서!

 

범위 값만큼 값 더해주면 끝!

 

 

사실 이제 어제 체스문제를 풀면서

O(N^2)이지만..

O(N)의 방법이 있다고 하면서
나에게 구간 합에 대해 이야기해 주었었다.

 

나는 따로 그 내용을 적어내진 않았지만

대충 내용은...

데이터를 입력받는 동시에 누적합을 더해서 배열 안에 넣어놓는 것..

 

이 누적합의 식은

S [i] = S[i-1] +v [i] 

으로

S[i] 전체 누적합은

S[i -1] 기존의 누적합 

+ 더하기

v[i] 다음 수이다.

이렇게 S [0]을 0부터 시작한다면

0 + 1 = 1

1 + 2 = 3

3 + 3 = 6

...

이렇게 이어지게 되는 것

그래서 누적합의 식은 그렇다!

 

그래서! 208번째까지 다 더하면 얼마야? 일 때

그냥 S [208]을 보여주면 끝

 

이 과정을 입력 때 동시에 하면 두 번 해줄 필요가 없다.

 

 

그래서 입력받는 값을 A = 1, 2, 3, 4, 5

누적합 S = 0, 1, 3, 6, 10, 15로 해주면

 

i부터 j까지의 합을 구하라고 할 때

 

3부터 5까지 라면

S [j] - S [i-1]

인 것.

왜 -1을 해주냐면

 

S [j] - S [i] 이게 되면?

S [5] = 15

S [3] = 6

15 - 6 = 9가 된다.

하지만 3부터 5까지 더하면 3+4+5 = 12가 되어야 한다.

즉 3을 남겨놔야 한다는 것..!

그래서 S [2]를 해줘서 3을 해줘야

12가 된다.

 

3부터 5까지 더해야 하니까 2까지 빼주면 되어서! 2를 빼주기 위해! -1 해준다!

 

이렇게 두 개의 식만 알면!

충분히 풀 수 있다.

---

 

이번문제는 좀 어려웠다.

누적합을 사실 어제 대충 읽었지만..

어려웠다.. 역시 대충이라 그런가..ㅎ?

크크..

어려웠던 문제인 만큼 내일 복습..?! 도 잘해봐야겠다..ㅎㅎ

 

고생했으!

 

그리고!!

하나도 안쉽다고!!!!!!!!!

쉽게 푸는 문제 절대 아닌 문제를 풀었다.