영화수집 문제) 카운팅트리에서 궁금한게 생겼습니다.

안녕하세요 mch님 ㅎㅎ

while(i>=0) 으로 바꾸어보았는데

>>

int sum(int idx){
    int ret = 0; 
    while(idx > 0){
        ret += tree[idx];

이부분은 tree를 기반 - 1부터시작하기 해야 하기 때문에 idx > 0으로 해야 합니다.

애초에 로직자체가 꼬여버리게 됩니다. 이진법 - 1, 2, 4 등을 기반으로 만들어진 펜윅트리기 때문이기 때문에 >= 0으로 해버리면 0을 참조해버리고 idx -= (idx & -idx); 이 부분 자체도 꼬여버리게 되서.. 애초에 0을 참조하지 않게 만들어야 합니다.

사실 오답이어야 하는게 아닌가 싶어 질문드립니다.

>>

update_idx = 100000

Update(update_idx , 1);

mp[temp] = update_idx--;

넵 mch님 말씀이 맞습니다. ㅎㅎ

10만으로 하면 안됩니다.

저게 근데 정답이라고 뜬게 이상하네요. 제가 시도했을 때는 시간초과가 발생합니다.

http://boj.kr/744e91340d4a431093fc6620c59daa63

dist[a][b] = dist[a][b] ? min(dist[a][b],c) : c;

이 부분 dist[a][b] = min(dist[a][b], c); 이렇게 해도 괜찮지 않나요?
>> 이거는.. 플루이드 문제 - 해당 문제 : 질문 에서 맞는코드, 틀린코드 두개로 다시 질문부탁드립니다.

벨만 포드에서
왜 (정점-1)번 순회를 해야하는지 잘 이해가 가지 않아서.. 사이클..

>>

벨만포드 사이클 찾는 방식을 보시면..

알고리즘의 작동 방식

1. 초기화: 시작 정점을 제외한 모든 정점의 거리 값을 무한대로 설정

2. 검사 -> 완화 : 모든 간선에 대해, 간선을 통해 다른 정점으로 이동하는 것이 더 짧은 경로를 제공하는지 검사하고, 필요한 경우 거리 값을 갱신합니다.

3. 순회 횟수: 이 과정을 각 정점마다 반복합니다 근데 이때 마지막 정점에까지 왔는데 v - 1 이상황에서도 완화할 부분이 있다면 사이클이 있는 것은 자명하기 때문입니다 혹시 모든 정점을 탐색하고 마지막 정점이 남았다 = v - 1 이므로..

   
   

   어떤 최단 경로도 한 정점을 두 번 이상 지나지 않습니다(사이클이 없는 경우).

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요 mch님 ㅎㅎ

혹시 어떤 문제인가요?