3개로 묶었을 때 그 중 가장 작은 옷값은 할인을 해준다 그럼 그리디로 생각해서 묶으면 된다 어차피 제일 큰건 할인 못받는다 3*k 번째로 큰 애들만 할인 받을 수 있다 편하게 pq에 값을 넣고 탐색해보자! 자바는 min heap 이므로 -를 붙여서 넣으면 최대힙으로 바꿀 수 있다 그리고 pq에서 하나씩 꺼내보며 만약 3*k 번째 옷이라면 값을 더하지 말자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import java.util.PriorityQueue; import java.util.Scanner; public class Solution { public static void mai..
숫자 제한들이 아주 작아서 그냥 제한 생각안하고 돌려도 잘 풀리는 문제다! 일단 인구이동을 어떻게 시킬지 생각해보자 간단하게 DFS를 이용하면 된다 나와 인접한 마을중 인구수 차이가 L이상 R 이하라면 그곳의 인구를 더해주고 체크해주자 이렇게 내가 갈 수 있는 마을의 모든 인구를 더하고 순서를 order에 담아 기억해주자 그럼 dfs가 끝나고 인구의 총 합 / 탐색한 마을로 order를 통해 사이좋게 나눠가지면 된다 이걸 언제까지해야할까 그냥 이동 할 일이 없을때까지 해보자! 이동이 없을 조건은 나 자신만 탐색하고 끝나는 경우다 그걸 cnt의 수가 1이하라면 안하는걸로 했다! 쉽게 생각하고 생각없이 짜면 잘 풀린다..! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..
다이어트를 하기위해 최적의 햄버거를 찾는 최고의 문제다 실생활에서 우리가 마주칠수있는 현실적인 문제 굿 일단 이 문제는 DP를 이용해서 풀 수 있다 내가 L 칼로리 이하를 먹어야만한다 그럼 N개의 버거 중 1) 현재 버거를 먹을때 2) 현재 버거를 안먹을때 두개를 비교해주면 된다 이 때 현재 버거를 먹기위해선 칼로리(sum+b[pos])가 L 이하여야 한다! 그럼 그 값들 중 최대값을 찾아보자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 import java.util.Scanner; public class Solution { public stati..
문제를 읽으면 그냥 다익스트라처럼 생겼다 그래프를 그리고 내가 최소시간을 들여 원하는 정점으로 가면 된다 근데 조건이 하나 붙는다 100을 초과는 거리를 간다면 그때는 연료를 충전해야 한다 이걸 매번 정점에서 하는줄알고 처음에 틀렸다 ㅎㅎ 결국 내가 갈수있는 거리도 하나의 가져가야할 데이터가 되므로 테이블을 d[정점의 수][갈 수 있는 거리]로 잡아보자 => d[1010][111]; 최대 정점은 1000개고 갈수있는 거리는 한번에 100이다 그리고 다익스트라를 돌리면서 pq에서 내가 남은거리도 들고다니면 된다 만약 남은거리보다 다음정점까지 거리가 같거나 짧으면 그냥 가면된다 하지만 남은거리가 더 짧으면 시간 5를 추가해 충전하고 주행가능거리를 100이라고 생각하자! 그리고 마지막으로 정점 n+1에서 남은..
문제를 푸는것보다 이해하는게 더 어려운 문제같다 문제를 풀려면 그냥 쓰여져있는대로 코딩하면 된다! 하라는대로!! a와 b가 i-1이하기 때문에 무조건 이전에 계산한 식을 통해 값을 구할 수 있다 그럼 for문을 통해 N-1개의 값들을 먼저 저장하고 그걸 이용해서 f(x)값을 구해보자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 import java.util.Scanner; public class Solution { static class Node { int tx,ax,bx; Node(int _t..