SH

BOJ Link https://www.acmicpc.net/problem/1202   풀이 과정우선순위 큐를 2개 사용한다.보석을 무게 기준 오름차순 정렬한다. 가방을 무게 기준 오름차순으로 우선순위 큐(kq)에 넣는다. (kq)에서 무게가 작은 가방부터 탐색하며, 다음 과정을 반복한다. 1. 현재 보석을 가방에 담을 수 있다면, 우선순위 큐(vq)에 보석의 가치를 내림차순으로 저장한다.해당 보석을 vq에 넣었으므로, 다음 가방에서 보석을 넣을 수 있는지를 탐색할 시작점인 idx를 올린다. 2. 담을 수 없다면, 뒤의 보석들도 담을 수 없으므로 탐색을 종료한다. 3-1. vq에는 현재 가방으로 낼 수 있는 가치가 내림차순으로 정렬되어있다. peek값을 ans에 누적하고 가방과 보석을 사용 처리한다.3-2..

BOJ Link https://www.acmicpc.net/problem/1011  풀이 과정다른 행성에 도달하기 직전의 칸은 k가 1이여야 한다.그렇다면, 러프하게 1 - (k올림) - max - (k내림) - 1의 꼴로 k가 전개됨을 알 수 있다. 몇 개의 케이스를 만들어 봤을 때, 1. k가 올림 - 내림 - 올림 등인 변칙적인 경로일 때 값이 최적인 경우는 없다고 생각했다.2. 값을 누적했을 때, 더이상 k를 증가시킬 수 없다면, 경로에 사용되었던 k들로 모든 답을 구성할 수 있다고 생각했다.(아마 최대 2번 더 사용해서) 그래서, 현재 이동한 거리 sum과 k를 비교하여,1. dis 2. dis > sum + k + (k + 1)라면, 사용된 k중 가장 큰 수부터 비교하며 최적해를 찾는다.로 구..

BOJ Link https://www.acmicpc.net/problem/1195     풀이 과정아이디어를 떠올리긴 쉽고, 구현은 실수하기 쉬운 문제였다. 1or2의 이진 값이기에 비트마스킹을 적용할 수 있고,각 기어의 길이는 100이하이므로,first 기어의 왼쪽/오른쪽에 값이 0인 100길이의 인덱스를 pad로 놓은 first[100 + first.len + 100]배열을 구성하여인덱스 처리를 쉽게 할 수 있다. 후자의 방법이 생각은 났지만 사용하지 않았다. 쉽다고 착각하여 무작정 코드를 작성하고 테스트케이스를 넣으면서 쓴맛을 봤다.  second 기어가 first 기어의 왼쪽에 있을 때, 겹칠때, 오른쪽에 있을 때 3개의 케이스를 나누어 완전탐색했다.이 때, 기어가 겹치는 2번째의 경우는 seco..

BOJ Link https://www.acmicpc.net/problem/1106  풀이 과정문제에서 호텔의 고객을 적어도 C명 늘려야 하기 때문에, C보다 고객이 많은 경우도 고려해야 한다.한개의 홍보로 얻을 수 있는 고객의 수는 100보다 작거나 같은 자연수이므로, C+100명까지 dp에 기록한다.이후, C~C+100번째 dp중 최소 값(홍보비용)을 출력한다. 또한, 배낭 문제를 1차원 dp로 다룰 수 있다.이때, Bounded(0-1) Knapsack인 경우 맨 뒤 인덱스부터 탐색해야 하며,해당 문제는 Unbounded Knapsack이므로 앞의 인덱스부터 탐색한다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java...

BOJ Link https://www.acmicpc.net/problem/1047  풀이 과정나무의 개수 N=40이다. 조합으로 접근할 수 없다.대신에, 울타리(직사각형의 영역)의 관점에서 생각한다. 나무의 좌표를 정렬한 배열을 통해, 탐색할 모든 영역을 구한다.이는 총 O(N^5)이며, 나무의 개수가 작으므로 가능하다. 1. 어떤 나무들을 모두 포함하는 울타리의 최소 둘레는, (가로변 길이+ 세로변 길이) *2이다. 이를 위해 꼭짓점 좌표 4개를 구해준다. 이 때, 가로/세로 길이가 0이 될수 있으므로 xleft==xright, yleft==yright인 경우도 고려한다. (O(N^4)) 2. 구성한 울타리를 기준으로, 안에 있는 나무와 밖에 있는 나무를 구해준다. 여기서 밖에 있는 나무란, 사실상 해..

BOJ Link https://www.acmicpc.net/problem/1234   풀이 과정dp[n][r][g][b]을 선언 후, bottom-up dp로 진행한다. n번째 레벨을 채우는 방법은 3가지이다. 1. 한 가지 장난감으로 꾸밀 때n-1의 dp에서 한 장난감을 n개 빼준다.경우의 수는 이전과 동일하므로, n-1번째 dp와 같다. 2. 두 가지 장난감으로 꾸밀 때해당 경우가 가능하려면, n이 2의 배수여야 한다.r=2, g=2 두가지 장난감으로 n=4의 레벨을 채운다면,2개의 자리에 r을 채운 후, 나머지를 g로 채운 것과 같다. (어떤 장난감을 먼저 배치해도 상관 없다.)r만 채운다면, g는 자동으로 올바르게 채워진다.따라서, 이는 곧 4C2이다. 3. 세 가지 공으로 꾸밀 때해당 경우가 가..

BOJ Link https://www.acmicpc.net/problem/1949   풀이 과정트리에서의 다이나믹 프로그래밍(+dfs) 문제다. 우선 임의의 정점을 루트로 잡고, top-down dfs로 리프 노드로 이동한다. 이후, 부모의 dp배열dp[parent][1]  - 우수 마을일 때dp[parent][0]  - 우수마을이 아닐 때 를 bottom-up으로 다음과 같이 채워나간다. 한 노드가 우수 마을 이라면, 인접한 노드는 모두 우수 마을이 아니여야 한다. 따라서,dp[parent][1] += dp[child][0]; 를 자식의 개수만큼 반복한다. 한 노드가 우수 마을이 아니라면, 인접한 노드는 우수 마을일 수도, 아닐 수도 있다. 따라서,dp[parent][0] += Math.max(dp[c..

BOJ Link https://www.acmicpc.net/problem/1041   풀이 과정그리디 + 구현 문제이며, 간만의 하드 코딩이였다. 1. 한 개의 주사위 구성하기 한 개의 주사위에 대해, 문제에서 요구하는 경우는 3가지이다.그리디 하게 정답을 구성할 수 있으므로, 아래의 값만 사용하여 최종 주사위를 구성한다. 주사위의 한 면만 보일 때 (min1)한 면의  최소값이다. 주사위의 두 면만 보일 때 (min2)인접한 두 면의 최소값이다.A면과 F면처럼 두 면이 수평한 경우를 제외하고 모든 경우를 구해준다. 주사위의 세 면만 보일 때 (min3)인접한 세 면의 최소값이다. 조합의 응용으로 구할 수 있나 생각했지만, 이는 꽤나 고려해야할 조건이 생긴다.대신, 하드 코딩으로 i번째 면과 두개의 면이..

BOJ Link https://www.acmicpc.net/problem/19580   개요정렬 + 우선순위 큐 + 그리디 문제이다. 추가 시간이 없는 문제라 Java로 풀시 까다롭다.O(M+N+(M+N)log??) 코드로도 시간 초과를 받았다.이후 sort 2번 + pq 1개 코드에서, pq 3개로 바꿔서 통과했다. 풀이 과정탐색 이전에, 시민을 마스크를 사려는 최소 가격(s)기준 오름차순으로 정렬한다. 이후 마스크를 가격(price)기준 오름차순 정렬한다.(s가 같다면 최대 가격(e)기준 오름차순 정렬할 필요는 없다.) 이후 탐색한다. 이 때, 정렬 후 판매할 수 있는 시민 후보를 담은 우선순위 큐를 별도로 사용해야 하는 이유는 다음과 같다. 우선 순위 큐를 사용하지 않을시, 첫번째 시민의 s가 2이..

https://softeer.ai/practice/7727 HAST 모의고사를 경험했기에, 외부 IDEA를 쓰지 않는 것에 익숙해졌다. 때문에 자바 Docs를 보지 않고 진행할 수 있었다. 그래프 탐색 문제이며, 나는 DFS로 구현하였다. 시간 복잡도최대 3명의 친구가 각각 3번씩 움직인다. 이를 delta 배열(4)로 구현하면,O(4^(3*3)) = O(262144)가 나온다. 충분히 브루트포스 할 수 있다. 친구들은 같은 칸에 방문할 수 있으며, 해당 경우엔 값을 한 번만 누적한다.나는 방문체크 배열만 기록하고 마지막에 계산하는 방식을 선택했다.(방문 횟수는 딱히 상관 없으므로 boolean 배열로 구현해도 된다.) 또한, BFS를 사용한다면, 형상 복귀가 까다롭다. 때문에 DFS를 사용했다. 각 친..