kdhsong   2달 전

맞게짠거같은데 

시간초과가뜨는데 이유를알수있을까요

펜윅트리로 짜야하나요 ?ㅠ

plzrun   2달 전

네 맞게 짜셨는데요,


제가 문제를 보지 않았는데 좀 아닌거 같은 부분이 있어서 그 부분만 수정했더니 맞았습니다.


먼저 MIN, MAX를 매크로로 쓰셨는데,

여기서 매크로 쓰시면 주의해야할 점이 절대 함수값을 파라미터로 넘겨주면 안됩니다.

할 때마다 호출하거든요. (그니까 함수의 값이 넘어가서 min, max를 계산하는게 아니라 min, max한번 할때마다 함수를 계속 호출하기 때문에 min max 매크로는 지양하는 편이 좋습니다.)


그래서 원래 std::min, std::max를 썼습니다.




그리고 부분합이 아닌문제에 펜윅을 적용할 수 있는지는 모르겠습니다.

아마 안되는게 아닌가.. 로 생각됩니다.

plzrun   2달 전

그리고 배열 크기 3배만 곱해도 맞았다고 뜨네요?

전에 종만북에서 4배는 해야한다고 배웠었는데.. 잘 모르겠네용


계산해보니까 26만 3천정도 잡으면 되긴하는데..




아.. 이게 10만이라서 그렇구나.. 2^N에 가까워진 경우에는 4배를 해야겠네요 ! :ㅇ

ㅎㅎ

rhs0266   2달 전

펜윅트리 두개 쓰면 세그먼트트리를 흉내낼 수 있습니다.

펜윅은 2N 만 잡아도 되는데, 세그먼트도 마찬가지일 것 같네여.

plzrun   2달 전

rhs0266

ㅇㅇㅏ 그렇군요 ㅎ

가만히 생각해보니 펜윅으로 최대, 최소 구하는 것도 그냥 부분합이 아닌 그 구간의 최대 최소만 가지고 있으면 되니까 가능할거라고 생각이 되는데, 왜 2개를 써야하는 건가요??

그리고 공간의 경우에는 세그트리가 4N이 맞다고 생각이 드는데요. 펜윅이 세그보다 공간이 반만 필요하잖아요? 아닌가요??



kdhsong   2달 전

너무너무감사드립니다!!!

rhs0266   2달 전

아 부분합에 대한 말이었습니당

흠... 동적으로 결국 단말노드에는 (i,i) 만 있고 위로 올라가면서 합치면 될 것 같았어요

펜윅이랑 노드가 관할하는 구간의 정의가 비슷하니까..? 정확한 건 아니네요 ㅜㅜ

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