Red Salmon

출처 : https://www.acmicpc.net/problem/1967

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1967.cpp

이 문제는 다풀어놓고 한참을 틀렸던 문제이다. 어처구니 없이 모든걸 만들어놓고 틀렸다 ㅠㅠ 왠지 작년에 본 삼성 SW역량 시험이 생각났다.. 다만들고 문장하나를 생각하지 못했던...

아무튼 문제는 가장 긴 구간을 찾는것이다. 

당연히 어떤 구간이 긴지 모르므로 전부 검색해봐야한다.

나는 DFS를 활용하였다. 여기서 내가 놓친 부분이 그것이다. 최대 지름을 구하는 문제이므로 2개의 길이만 필요하다. 

그리고 문제에서는 이진트리 느낌으로 보여졌는데, 실제 데이터에는 이진트리가 아닌것들도 많다. 자식노드가 여러개인경우 말이다.

사실 이정도면 미리 문제에서 알려줘야하지 않나..싶다.

알고리즘은 다음과 같다.

1. 벡터를 사용하여 연결된노드와 값을 입력한다.

2. 함수를 호출하는데 인자는 루트노드만 보내준다.

3. 각 루트노드에서 연결된 간선을 전부 탐색하고 그 간선의 값을 더해본다. 

4. 그리고  temp와 val[2]를 활용하여 val[2] 에는 가장 긴 2개의 녀석만 담아둔다.

5. 그 2개의 값의 합이 ans보다 큰지 비교를 한다.

6. 리턴은 그 2개에서 가장 긴녀석을 리턴한다.

이 과정이 반복이되면 딱 한번 모든 노드를 검색하게 되고 자연스레 답이 담기게 된다.

뭐랄까..예전엔 이런 DFS가 조금 힘들었는데 이젠 뭐...그냥 술술 풀린다. 그래도 실수한건 실수한거다. 문제를 잘 읽어야겠다.

출처 : https://www.acmicpc.net/problem/11441

정답 : https://github.com/stemp12/acmicpc.net/blob/master/2016.01/11441.cpp

이 문제의 풀이는 이미 내가 과거에 풀어본 배열내 구간 계산이므로 세그먼트 트리를 적용시키면 된다. 설마 이 문제를 읽고 구간 a부터 b까지의 합을 계속 더하고 더하고 하는 사람은 없을것이다. 무조건 TL이 나올것이다.

세그먼트 트리도 정답이지만 이 문제는 조금 더 생각하면 다른 해법도 있다.

어차피 구간내의 합이기 때문에 0부터 계속 더해나가는 것이다. 즉

a[0]=a[0]

a[1]=a[1]+a[0]

a[2]=a[2]+[1]

a[3]=a[3]+a[2]

이렇게 하면 구간 0부터 n까지의 합이 계속 저장이 된다. 그리고 입력으로 구간이 입력이 되면 그 구간을 빼주면 된다.

즉 a~b구간의 합은 0~b구간의 합에서 0~a구간의 합을 뺀다면 a~b구간의 합이 되는것이다. 이렇게 푸는것도 간단히 푸는 방법이다.

그러나 나는 세그먼트트리 연습겸 저렇게 풀어봤다.

이런 문제가 참 괜찮은 문제라고 생각한다.