알고리즘을 좋아하는 나

플로이드 워셜이랑

disjoint-set을 사용했다.

Sort는 Collection.sort내장 소트 사용

최대 값이랑 합이랑 헷갈려서 몇번틀림...

와.. 문제를 푸는데 2시간이 걸렸다.

코드에 변화가 2번이 일어났는데, 처음에는 subproblem을 너무 쉽게 생각했고,

그 다음에는 반복문 내용을 수정했다..

풀이 방법은

위에 1x2랑 1x1로 채우고 밑에를 n-1로 해줘서 d[n-1] * 2

그리고 2x1, 1x1로 채우고 밑에를 n-2로 채워서 d[n-2] * 3

그리고 1x2, 2x1, 1x1을 전부 사용해 위에를 채운건 d2[n-1]+d[n-3] * 2

합치면 d[n-1]*2+d[n-2]*3+(d2[n-1]+d[n-3])*2

일곱난쟁이의 키는 합쳐서 100이다.

100M인가? ㅋㅋ

근데 9명이 되버린것.

그래서 2명의 키를 빼준값이 100이되면 된다.

LinkedList를 이용해서 간단하게 풀었다.

다익스트라에 이어서 플로이드 워셜 알고리즘을 공부했다.

다익스트라를 모든 정점에서 돌리면 플로이드 워셜이 된다.

그런데 다익스트라는 음수 가중치를 가지는 간선이 있으면 안된다 한다.

플로이드 워셜은 모든 정점을 돌아보기 때문에 시간복잡도가 O(V^3)이다.

입력에서 중복값 확인을 해주니 정답이 됐다.

위키백과에 JAVA코드도 추가했다.

위키백과 JAVA

disjoint-set 을 처음 공부했다.

서로소에 대해서 기억이 가물가물해 찾아봤는데, 서로 다른 숫자의 집합.

이 문제는 disjoint-set에 대해 기초만 알면 되는데, find, link만 알면 된다.

나무위키에 올라온 사진들을 보며 코드를 작성했다.

MAX값을 2147483647 즉 signed int 의 MAX로 하다보니, 출력에서 꼬여가지고 출력초과과 떴었다.

백준의 출력 용량은 최대 1 MB이다

그 다음에 MAX값을 변경해서 제출하니 시간초과가 뜨는 것이다.

우선순위 큐로 작업하지않고, 리스트에 다 담아서 작업했었음.

그래서 큐에서 값이 변경될 경우에 offer해줬고, 성공했다.