굥굥

누적 합이라는 개념을 처음으로 알고 적용시킨 문제이다. 먼저 누적 합을 설명하자면 다음 그림과 같다. 인덱스 2의 누적합은 인덱스 0 + 1 + 2 까지의 값이다. 식으로 표현하면 S(n) = S(0) + S(1) + ... S(n-1) + S(n) 이라고 하는데 그냥 전까지의 합이라고 생각하면된다. 모든 배열의 값이 특정 인덱스까지의 합이므로 S(n+1) = S(n-1) + arr[n] 을 하면 된다. (S(n)은 n까지의 누적합.) 특정 인덱스에 대한 값만 구하고 싶다면 S(n) - S(n-1) 을 해주면 된다. 다시 문제로 돌아와서 보면 펄스값에 따라 값이 양수/음수 로 바뀐다. 근데 어짜피 절대값은 바뀌지 않으므로 최대, 최소 값만 구해주면 된다. 펄스값은 1, -1, 1 ... 이든..

(코드 추가) 문제를 다 풀고 다른 공부하다가 문득 들은 생각인데 어짜피 모든 경로는 정해져 있다. 그리고 도착해야하는 목적지가 모두가 같으므로 도착지에서 각 노드별로 bfs를 모두 돌며 얼마나 떨어져있는지 count 를 전부 계산한다. 그리고 sources에 있는 인덱스별 답만 추출하면 되는 문제였다... 수정해서 돌려보니까 정말정말정말 빨라졌다... 왜 처음엔 이 생각을 못했을까..ㅋㅋ 뿌듯하기도하고 당황스럽기도 하다. 큐를 이용한 너비 우선 탐색으로 문제를 풀었다. 문제를 풀기 전에 어떤 섬이 어느 섬들과 연결되어 있는지에 대한 정보를 먼저 정리하고 시작했다. 입력으로 [[1,2] , [2,3]] 이 주어지면 1 -> 2 2 -> 1, 3 3 -> 2 로 정리된 벡터를 하나 만들었다. ..