전체 글 썸네일형 리스트형 BOJ)13016 내 왼손에는 흑염룡이 잠들어 있다 문제: icpc.me/13016 오랜만에 문제 포스팅을 한다. 문제를 요약하면 한 정점 v에서 다른 정점으로의 최단거리를 dist[i] (i: 1~n) 이라고 했을 때, dist[i]의 최댓값을 모든 정점 v에 대해 구하는 문제이다. 물론 한 정점에서 dist[i]의 최댓값을 구하는건 dfs를 수행하여 쉽게 해결할 수 있지만 모든 정점에 대해 구하게 될 경우 정점의 개수가 5만이므로 시간초과를 보게 될 것이다. 하지만 조금 생각해보면 한 정점에서의 부터 다른 정점으로 부터의 최단 거리 중 최댓값은 트리의 지름의 양 끝 단말 노드 중 하나로의 거리라는 것을 알 수 있다.(만약 트리 지름의 단말 노드가 아닌 다른 리프로 부터의 거리가 최댓값이라면, 트리의 지름보다 긴 거리가 생긴다는 뜻이므로 모순이된다.) .. 더보기 SCPC 2018 이벤트 당첨! 살면서 이런 이벤트와는 인연이 없다고 생각했는데 어제 갑자기 문자가 왔다. 커피 당첨됬다고 ㅋㅋㅋ 올해 SCPC는 본선에 나갈 수 없겠지만(7월 입사 ㅠㅠ... 게다가 일본 여행 날짜와 2차 예선 날짜가 겹친다 ...) 커피라도 받게되서 기분이 좋다 더보기 BOJ)15673 헤븐스 키친2 문제 :http://icpc.me/15673 n개의 수열이 주어질 때, 연속 된 두 구간을 선정을 한다. 두 구간을 a,b라하면 구간 a의 합과 구간 b의 합의 곱의 최댓값을 구하는 문제이다. 생각해보면 구간 a의 합과 구간 b의 합의 최솟값들을 곱하는 경우와, 구간 a의 합과 구간 b의 합의 최댓값들을 곱하는 경우가 답의 후보가 됨을 알 수 있다. 구간 a가 i~j 구간 b가 k~l 이라고 해보자. k를 고정시킨 뒤 생각해보면 구간 k~l의 합은 psum[l]-psum[k-1]이므로, k보다 크거나 같은 범위의 psum의 최댓값과 최솟값을 가지고 있으면, 구간 b의 최댓값과 최솟값을 구할 수 있다. 그럼 i~j 구간의 최댓값과 최솟값은 어떻게 처리할 수 있을까? 구간 i~j의 합은 psum[j]-psu.. 더보기 이전 1 2 3 4 5 6 7 8 ··· 118 다음
