zmfldlwl   4년 전

예를 들어

5

3 2 0 4 1

과 같이 정렬되지 않은 input이 들어오게된다면...

결과값을 계산해보면

1

1 + 3

1 + 2 + 4

2 + 1 + 1 + 3

1 * 4 * 7 * 7 = 196이라는 output이 나와야 합니다.

그런데, 각 구간의 거리들이 모두 독립적인 값들이라서 그 다음 값들에 영향을 미치지 않을거 같아서...

펜윅을 어떤식으로 적용시켜서 문제를 풀어가는 로직을 구상해야할지 감이 안오네요...

하루종일 보고 있어서 제자리걸음인거 같아서 질문 올립니다...

chogahui05   4년 전

x번째 나무를 loc의 위치에 심어야 한다고 해 봅시다.


(1) loc보다 크거나 같은 좌표에 있는 나무들의 갯수 : x개

(2) loc보다 크거나 같은 좌표에 있는 나무들의 좌표의 : sum_one

(3) loc보다 작은 좌표에 있는 나무들의 갯수 : y개

(4) loc보다 작거나 같은 좌표에 있는 나무들의 좌표의 합 : sum_two


현재 기준점은 loc입니다.

loc보다 크거나 같은 경우에는 나무 좌표 - loc이 거리가 되겠네요.

각 나무마다 loc을 빼기 때문에

sum_one - loc * x이 되고요.


loc보다 작은 나무들은

(loc - 나무 좌표)가 거리가 되는데요.

이건 loc * y - sum_two로 계산할 수 있죠.


예를 들어서

5

[3 2 0 4] 1

이 있다고 가정하고, 1에 나무를 심는다고 가정해 봅시다.


그러면 1보다 크거나 같은 나무의 갯수는 3 = x

그것들의 좌표의 합은 9 = sum_one

1보다 작은 나무의 갯수 1 = y

그것들의 좌표의 합은 0입니다. = sum_two

현재 loc = 1이고요.


sum_one - loc * x +  loc * y - sum_two에 대입하면

9 - 1 * 3 + 1 * 1 - 0 = 9 - 3 + 1 = 7이 됩니다.

zmfldlwl   4년 전

짠다고 짜봤는데... 계속 틀렷다고만 나오네요 ㅠㅠ

질문글들에 올려주신 인풋들도 제대로 결과가 뜨는데 ...

후 도대체 어떤 경우에 터지는 걸까요...


chogahui05   4년 전

오버플로우 체크해 보셨나요?

zmfldlwl   4년 전

오버플로우가 터졌었네요...

한 100개넣엏을때 안터지길래 ㅠㅠ 못찾앗는데

패스했습니다! 감사합니다.

wondy1128   4년 전

5

3 2 0 4 1

과 같이 정렬되지 않은 input이 들어오게된다면...

결과값을 계산해보면

1

1 + 3

1 + 2 + 4

2 + 1 + 1 + 3

1 * 4 * 7 * 7 = 196이라는 output이 나와야 합니다.


1*5*7*7

245 가 나와야합니다.


ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ저 입력으로 계속 해보고, 계산 안해보고 196 안나오길래 코드 한시간동안봤습니다ㅋㅋㅋㅋㅋㅋ


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