[백준/JAVA] 20303_할로윈의 양아치

백준🔗

20303번: 할로윈의 양아치

 

문제

 

 

간단 풀이

얼마 전 특강 수업에서 dp를 배웠는데, 이전에도 알고 있었지만 이번 수업을 통해 구체화된 풀이법을 다시 정리하게 되어서 연습할 겸 dp 문제를 풀어봤다.

 

dp를 할 때 아래의 2단계를 거치는 것이 핵심이다!

dp의 대표적인 문제인 배낭 문제를 예로 들어보면.. (부피가 정해진 가방에 부피&가치를 가진 물건들을 넣을 때, 물건들의 부피 합이 가방의 부피를 넘지 않으면서 가치의 합이 최대가 되도록 물건을 담아야 한다.)

1️⃣ DP 테이블 정의하기 

      미지수의 개수에 따라 DP테이블이 몇 차원이 될 지 결정된다.

      e.g. dp[i][j] : 물건이 1~i번까지 있고, 부피가 j인 가방으로 얻은 최대 가치 

2️⃣ 파티셔닝

      마지막 아이템을 기준으로 경우의 수를 나눠서 구하기

      e.g. 1) i번 물건을 사용한 경우 dp[i][j] = dp[i-1][j-부피[i]] + 가치[i]

             2) i번 물건을 사용하지 않은 경우 : dp[i][j] = dp[i-1][j]

 

 

이번 문제도 배낭 문제와 같은 원리로 접근했다.

다만, 친구들끼리는 하나의 그룹으로 묶을 수 있기 때문에 우선 친구인 아이들을 그룹별로 묶었고, 그룹 class는 우리가 필요한 정보인 인원수, 사탕 개수를 필드로 가지도록 했다.

이후 구하고자 하는 것은, 최대 인원이 K-1로 정해진 상태에서 (울고 있는 아이들 수가 K이상이 되면 어른들에게 들키기 때문에 최대 K-1명까지는 울어도 된다.) 인원수, 사탕개수를 가진 그룹들을 사탕 개수의 합이 최대가 되도록 선택하면 된다.

이제 배낭 문제와 유사해졌다는 것을 알 수 있다.

 

문제 상황이 정의가 됐기 때문에 dp 테이블 정의와 파티셔닝을 다음과 같이 해줬다.

dp[i][j] : 1~i번째 그룹까지 있을 때, j명의 사탕을 뺏어서 얻은 최대 사탕 개수

1) i번째 그룹을 포함하는 경우 dp[i][j] = dp[i-1][j-인원[i]] + 사탕[i]

2) i번째 그룹을 포함하지 않는 경우 dp[i][j] = dp[i-1][j]

 

 

※ 문제 제출 후 실행 시간이 짧은 다른 사람들의 코드를 살펴보니 dp 배열을 2차원이 아닌 1차원으로 정의해서 활용했을 때 메모리, 시간이 절약되는 것을 알 수 있었다!! 그래서 1차원으로도 바꿔보았다ㅎㅎ  

 

 

 

코드

 📌 dp 2차원 배열

import java.io.*;
import java.util.*;

public class Main {
	static List<Integer>[] friends;
	static boolean[] check;
	static int[] candy;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 거리에 있는 아이들 수
		int M = Integer.parseInt(st.nextToken()); // 친구 관계 수
		int K = Integer.parseInt(st.nextToken()); // 우는 아이는 K미만이어야 함
		st = new StringTokenizer(br.readLine());
		candy = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			candy[i] = Integer.parseInt(st.nextToken());
		}

		friends = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			friends[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			friends[a].add(b);
			friends[b].add(a);
		}

		// 친구들끼리 그룹 만들기
		List<Group> groups = new ArrayList<>();
		check = new boolean[N + 1];
		for (int i = 1; i <= N; i++) {
			if (!check[i]) {
				groups.add(makeGroup(i));
			}
		}

		// dp[r][c] = 1~r번째 그룹까지 있을 때, c명의 사탕을 뺏어서 얻을 수 있는 최대 사탕 개수
		int[][] dp = new int[groups.size() + 1][K];
		for (int r = 1; r <= groups.size(); r++) {
			for (int c = 1; c < K; c++) {
				Group g = groups.get(r - 1);
				// 1. c번째 그룹 포함하지 않는 경우
				dp[r][c] = dp[r - 1][c];
				// 2. c번째 그룹 포함하는 경우
				if (c >= g.people) {
					dp[r][c] = Math.max(dp[r][c], dp[r - 1][c - g.people] + g.candy);
				}
			}
		}
		System.out.println(dp[groups.size()][K - 1]);
	}

	static class Group {
		int people, candy;

		public Group(int people, int candy) {
			this.people = people;
			this.candy = candy;
		}
	}

	static Group makeGroup(int x) {
		Queue<Integer> q = new LinkedList<>();
		int pCnt = 0;
		int cCnt = 0;
		q.add(x);
		check[x] = true;
		while (!q.isEmpty()) {
			int cur = q.poll();
			pCnt++;
			cCnt += candy[cur];

			for (int f : friends[cur]) {
				if (!check[f]) {
					check[f] = true;
					q.add(f);
				}
			}
		}
		return new Group(pCnt, cCnt);
	}
}

 

📌 dp 1차원 배열

// dp[r][c] = 1~r번째 그룹까지 있을 때, c명의 사탕을 뺏어서 얻을 수 있는 최대 사탕 개수
int[] dp = new int[K];
for (int r = 0; r < groups.size(); r++) {
	Group g = groups.get(r);
	for (int c = K - 1; c >= g.people; c--) {
		// 1. c번째 그룹 포함하지 않는 경우
		// 2. c번째 그룹 포함하는 경우
		dp[c] = Math.max(dp[c], dp[c - g.people] + g.candy);
	}
}

 

 

참고 자료

백준 20303번 할로윈의 양아치