백준28 [백준 2156] 포도주 시식 DP문제입니다. 규칙은 2가지가 있는데 1. 한번 마시면 다 마시고 그 자리에 두어야 함. 2. 세잔을 연속으로 마시지 못함. 입니다. 저는 1번 규칙은 크게 신경 안쓰기로 하고. 2번만 보겠습니다. 일단 점화식을 구하기 위해서 현재 내가 선택할잔을 N으로 두겠습니다. N에 대해서 최대로 마실 수 있는 양을 구하는 방법은 1. 바로 앞(N-1)의 포도주를 마시고 그 앞의 앞 잔(N-3)을 먹은 상태에서 현재의 잔(N)을 먹는 방법 2. 앞의 앞(N-2) 포도주를 마시고 그 앞(N-3) 포도주를 마신상태에서 현재의 잔(N)을 먹는 방법 3. 바로 앞(N-1) 까지 최대치로 먹은 후 현재의 잔을 먹지 않는 방법 3가지가 있습니다. 그럼 (arr은 포도주저장한 배열입니다) 점화식은 D[N] = D[N-2] +.. 2019. 8. 4. [백준 1011] Fly me to the Alpha Centauri 오랜만에 문제 몇개 풀다가 올려봐용. 일단 이 문제를 풀기 위해서 저는 그냥 그림을 그려봤습니다. x y 가 0 11 인 상황의 그림을 봐볼게요 (x는 start로, y는 end로 하겠습니다) 처음 출발은 1칸으로 출발시킨다고 문제 그림에 나와있고, 도착도 1칸으로 도착해야된다 써있습니당 그래서 1. start와 end부터 번갈아가며 점프를 1칸, 2. 점프 후 사이에 거리가 있다면 점프를 1칸 늘려서 다시 start와 end에 번갈아서 해줍니다. ( 점프 횟수가 최소이여야 하기 때문에 최대한 뛸수있는 만큼 뛰어야함) 이렇게 진행하면 그림처럼 두개의 위치가 겹쳐버리는 곳이 생깁니다. 그럼 다시 그림의 맨 밑 박스상황에서 남은 점프거리가 2일 경우로 가서, 남은 2칸은 앞에서 3칸을 뛰었기 때문에 2로 정.. 2019. 7. 31. [백준 11047] 동전 0 그리디 알고리즘으로 해결하는 문제입니다... 사용할수 있는 동전 중 제일 큰 동전을 하나씩 쓰면 됩니다. 2019. 4. 23. [백준 1753] 최단경로 다익스트라 알고리즘 문제입니다. 일단 그래프를 인접행렬로 구현하게 되면 메모리 초과가 발생할거 같아 ( 정점 최대 갯수 20000 ) 인접 리스트로 구현했습니다. 처음에는 그냥 우선순위큐에 다음 위치 ( Integer로) 를 저장해 쓰다가 시간초과를 바로 먹었습니다. (원래 매 루프마다 방문하지 않은 정점 중 시작점으로 부터 가장 가까운 정점을 뽑는게 당연함. 안해서 빠꾸먹음) Comparator를 하나 만들어 거리가 가장 가까운 녀석이 높은 우선순위를 가질 수 있도록 합니다. while문의 변수 이름들이 상당히 지저분한데 우선순위 큐의 제너릭이 Integer에서 NextNode로 변했기 때문에 대충 고쳐서 통과만 시켰지만 보기엔 좀... 2019. 4. 22. 이전 1 2 3 4 ··· 7 다음
