생각하며 풀어야하는 문제다! 이런 쉽게쉽게 생각하고 최적을 찾는 문제 잘푸는 사람들이 있던데.. 나는 아니다 ㅎㅎ 처음에 거꾸로 정렬시키고 투포인터로 뒤에서부터 보면 무조건 된다고 생각했다 근데 대충 테케를 만들어보다가 2 4 5 6 7 8 8 9 50 100 이걸 넣었다가 내 코드에서는 7이 나오는걸 발견했다 답은 6..! 생각해보면 최대답은 2/N이다 박스에 한개만 넣을수 있기 때문에! 그럼 우리는 반으로 잘라서 0~2/N, N/2+1~N 까지 l,r로 나눠서 넣어보면 된다! 풀고나면 참 쉬워보이는 문제.. 근데 한번에 떠올리기가 참 쉽지않다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include #include using namespace s..
쉬운 문제라고 생각해서 풀었는데 틀렸다 그리고 계속 생각도 거꾸로해서 방법을 못떠올렸다 문제는 자기와 색이 다르고 나보다 작은공을 먹을 수 있다는 내용이다 문제를 보고 거꾸로 생각했다 미리 합을 다 구해두고 크기를 기준으로 거꾸로 정렬해서 현재 나의 크기의 합들과 나의 색들의 합들을 빼야지했는데 두개의 교집합 부분을 다시 더해주기가 힘들어서 못했다 찾아보니 완전 거꾸로 생각하고있었다 반대로가면 쉽다 내가 여태까지 본 크기의 집합들과 색의 집합들을 가져가면 오히려 쉽다 크기를 기준으로 오름차순 정렬을하면 나는 다음 볼에 영향을 주는 볼이다 결국 생각해보면 현재 볼 = (여태까지의 합) - (같은 수의 크기 합) - ( 같은 크기의 크기 합) + 내크기 이렇게 하면 된다 집합이라고 생각하니 그림이 그려진다 ..
처음 스터디하다가 배웠을 때 신기했던 문제다 이 문제는 다익스트라르 풀 수 있다! 다익스트라로 어떻게 풀어야할까 쓰레기는 최대한 안지나고 쓰레기 옆길도 안지나고싶다 그럼 가중치를 쓰레기에는 5000, 옆길은 1을 줘보자! 5000을 주는 이유는 나올 수 없는 값을 주기 위해서다 왜냐면 나중에 5000으로 나눌거라서 ㅎㅎ 문제를 푸는 방법을 생각해보자! 1. 먼저 가중치를 쓰레기는 5000, 쓰레기 4방향으로는 1을 주자 2. 그리고 다익스트라를 통해 목적지까지 간다면 최소비용으로 가는 길을 찾을 것이다 3. 그럼 우선순위는 빈칸-> 쓰레기 옆길 -> 쓰레기가 된다 4. 마지막으로 쓰레기를 지나쳤다면 5000a , 옆길을 지나치면 b라는 가중치가 있을것이다 => 5000a+b가 될테니 /5000을 한다면 ..
A형에 MST가 나왔다던데 이 문제다 완탐으로 풀 수 있는데 괜히 MST한번 써봤따 그리고 틀렸따~~! -1을 출력하는 경우를 잘 생각해야한다 mst에서 정점이 n개일때 간선은 n-1개다 이 성질을 생각해서 -1을 정해주면 예외가 사라진다! MST 자체를 만드는건 유니온 파인드를 이용해 할 수 있다 거리 순으로 정렬하고 만약 A,B 정점이 부모가 다르다면 merge를 시켜준다 그렇게 모든 정점을 연결하면 MST가 완성된다! 그럼 문제를 푸는 순서를 생각해보자 1. 먼저 각 섬마다 넘버링을 해서 섬을 구별시킨다 =>dfs 2. 그리고 각 섬에서 다른 섬으로 거리를 구해보자 이 때 직선으로만 가능하니까 그냥 완탐 돌리자 3. 모든 섬에 대해 그래프를 만들어준다 4. MST를 만들자! 소스코드 1 2 3 4 ..