Close
Close full mode
logo만렙 개발자 키우기

매출 하락 최소화

Git RepositoryEdit on Github
Last update: a year ago by nowwaterReading time: 2 min

문제

코드

코드 보기
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Team{
int upTeam = -1, downTeam = -1;
boolean hasTeam = false;
public Team(int upTeam, int downTeam) {
this.upTeam = upTeam;
this.downTeam = downTeam;
}
}
class Solution {
static List<Integer> adj[] = new ArrayList[300005], sales;
static int links[][], INF = 987654321;
static int cache[][] = new int[300005][2];
public static int solution(int[] Sales, int[][] Links) {
int n = Sales.length;
sales = new ArrayList<>();
links = Links;
sales.add(0);
for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList<>();
}
for (int sale : Sales) sales.add(sale);
for (int[] link : links)
adj[link[0]].add(link[1]);
dfs(1);
return Math.min(cache[1][0], cache[1][1]);
}
private static void dfs(int cur) {
// cache[cur][0] : cur 번째 노드가 참석하였을 때의 매출합의 최쇠
// cache[cur][1] : cur 번째 노드가 참석하지 않았을 때의 매출합의 최쇠
// leaf 노드이면 더 이상 구할 수 없음
if(adj[cur].isEmpty()){
cache[cur][0] = sales.get(cur);
cache[cur][1] = 0;
return;
}
int minGap = INF;
cache[cur][0] = sales.get(cur);
for (Integer x : adj[cur]) {
dfs(x);
cache[cur][0] += Math.min(cache[x][0], cache[x][1]);
minGap = Math.min(minGap, cache[x][0] - cache[x][1]);
}
if(minGap < 0) minGap = 0;
cache[cur][1] = cache[cur][0] - sales.get(cur) + minGap;
}
public static void main(String[] args) {
int sales[] = {14, 17, 15, 18, 19, 14, 13, 16, 28, 17};
int links[][] = {
{10, 8},
{1, 9},
{9, 7},
{5, 4},
{1, 5},
{5, 10},
{10, 6},
{1, 3},
{10, 2}
};
int sales2[] = {5, 6, 5, 3, 4};
int links2[][] = {{2,3}, {1,4}, {2,5}, {1,2}};
int sales3[] ={5, 6, 5, 1, 4};
int links3[][] = {{2,3}, {1,4}, {2,5}, {1,2}};
int sales4[] ={10, 10, 1, 1};
int links4[][] = {{3, 2}, {4, 3}, {1, 4}};
System.out.println(solution(sales, links));
System.out.println(solution(sales2, links2));
System.out.println(solution(sales3, links3));
System.out.println(solution(sales4, links4));
}
}

⭐️느낀점⭐️


> 마지막 문제는 Tree DP 유형 이었다. 처음 풀어봤는데 한참 고민하다가 풀었지만 틀리고 답안을 봤다. > > 답안을 봐도 한참동안 이해가 안되서 고생좀 했다..

풀이 📣


1️⃣ 각 루트 노드별로 자식 노드들을 리스트 배열을 통해 저장한다.

2️⃣ Tree DP 알고리즘을 적용하여 문제에 대한 설계를 다음과 같이 한다.

- cache[i][0] : i 번 노드가 루트인 서브트리에서 조건을 만족했을 때 매출합의 최소, i번은 참석
- 먼저 i 번 노드의 비용을 더해놓는다. 그러면 i번이 팀장인 서브 트리에서 자식 노드들은 선택하든 선택하지 않든 상관이 없으므로 그 중 더 작은 값을 더해주면 된다.
-> cache[i][0] += Math.min(cache[ci][0], cache[ci][1])
- cache[i][1] : i 번 노드가 루트인 서브트리에서 조건을 만족했을 때 매출합의 최소, i번은 불참석
- 따라서 cache[i][1] 을 계산할 땐 자식 노드중 누군가는 반드시 참석해야함.
- 자식 노드 중 참석했을 때의 손해(자식 노드가 루트인 서브트리에서 루트가 참석하였을 때의 최소 비용 - 루트가 참석하지 않았을 때의 최소 비용) 가 가장 적은 사람이 참석하면 됨.

3️⃣ cache[i][0] 을 구할 때, 만약 자식 노드를 선택하는 경우가 선택하지 않는 경우보다 더 최소비용이어서 자식 노드를 하나라도 선택했었다면 손해값에는 음수가 저장된다.

- cache[ci][0] 값이 cache[ci][1] 보다 작아서 손해값 minGap 에는 음수값이 저장된다.
- 하지만 cache[i][0] 에 자식이 하나도 포함되어있지 않았다면 cache[ci][0] 이 cache[ci][1] 보다 비용이 적은 경우가 없었다는 말이 되므로
mingap = cache[ci][0] - cache[ci][1] 에서 양수가 저장된다.

4️⃣ 이후에 cache[i][1] 을 구할 때, 자식노드가 반드시 하나는 포함되어 있어야한다.

- i번 노드를 포함시키지 않은 최소비용을 구한다 => cache[i][0] - sale[i]
- cache[i][0]을 구할 때 자식노드를 선택했었다면 cache[i][0] - sale[i] 에 i번 비용만 제외시켜줬으므로 이미 자식이 포함된 값이 들어있다.
따라서 이미 손해값(mingap) 이 min 비교로 0이 되었기 때문에 mingap 만큼 더해줄 필요가 없다.
- mingap : 자식들을 추가해야 하는 비용 중 가장 저렴한 비용의 자식 한명 치 비용

5️⃣ cache[1][0]cache[1][1] 중 최소 비용을 출력한다.


실수 😅

  • 트리 DP.. 쉽지 않은 녀석이었다.

  • 풀이를 3개나 찾아보면서 왜 저렇게 코드가 전개되는지 이해하려고 애를 썼다.

  • 결국 이해를 할 수 있었고 이해한 내용을 정리하면서도 몇 번이나 계속 이해가 안되는 부분이 생겼고 다시 해결하고 반복하였다.

👩‍💻 Problem Solving — Previous
카드 짝 맞추기
Next — 👩‍💻 Problem Solving
TIPS