da9dac

문제

접근 방식

각 스티커를 고른 상태 안고른 상태로 백트래킹으로 탐색하면

주어진 입력의 최대 범위로는 시간초과가 발생해 완탐으로 풀 수 없는 문제라

DP를 이용해 풀어야 한다.

DP로는 O(N)에 풀 수 있는데 우선 DP 테이블부터 만들어보자.

10 30 10 50 100 20 40
20 40 30 50 60 20 80

위와 같은 입력이 주어졌다고 가정하면

위와 같은 표가 만들어지고 2, 3번째 행이 DP 테이블에 저장될 값들이다.

우선 각 줄의 스티커가 선택될 수 있는 경우는

현재 줄의 이전 스티커를 사용하지 않았거나

현재 줄의 이전 스티커보다 현재 스티커를 사용하는게 더 효율적인 경우다.

즉, 현재까지 고른 스티커의 누적값을 DP[i][j]라 했을 때

(DP[다른 행의][이전 스티커 = j - 1] + 현재 스티커 값) == 현재 줄의 이전 스티커를 사용하지 않은 경우

(DP[다른 행의][2번째 전 스티커 = j - 2] + 현재 스티커 값) == 현재 스티커가 더 효율적인 경우

중에서 가장 큰 값으로 테이블을 채워주면 되고

테이블을 다 채운 후에 마지막 값 중 가장 큰 것이 정답이 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine()), n;

		while (t-- > 0) {
			n = Integer.parseInt(br.readLine());

			int[][] stickers = new int[2][n + 1];
			int[][] dp = new int[2][n + 1];

			for (int i = 0; i < 2; i++) {
				st = new StringTokenizer(br.readLine());

				for (int j = 1; j <= n; j++) {
					stickers[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			dp[0][1] = stickers[0][1];
			dp[1][1] = stickers[1][1];

			for (int i = 2; i <= n; i++) {
				int s1 = stickers[0][i];
				int s2 = stickers[1][i];
				dp[0][i] = Math.max(dp[1][i-1] + s1, dp[1][i-2] + s1);
				dp[1][i] = Math.max(dp[0][i-1] + s2, dp[0][i-2] + s2);
			}

			sb.append(Math.max(dp[0][n], dp[1][n])).append("\n");
		}

		System.out.println(sb);
	}
}

문제

접근 방식

결국 문제에서 요구하는건 두 우주의 행성들의 대소관계가 같은지를 판단하는 것이기 때문에

이분 탐색으로 좌표 압축을 한 후에 좌표 압축 결과가 같은 배열 쌍이 존재할 때마다

카운트를 1씩 증가시켜주기만 하면 된다.

20 10 30
10 20 60
80 25 79
30 50 80
80 25 81

예를 들어 위와 같이 5개의 우주마다 3개의 행성이 있을 때

행성의 크기 순으로 표현하면 다음과 같다

1 0 2
0 1 2
2 0 1
0 1 2
1 0 2

가장 작은 수부터 0이라고 표현 했을 때

행성의 대소관계가 일치하면 같은 행성이라고 볼 수 있기 때문에

1 0 2로 같은 1번과 5번 행성이 균등하다 볼 수 있고

0 1 2로 같은 2번과 4번 행성도 균등하다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());

		int[] arr = new int[n], sorted;
		int[][] zips = new int[m][n];

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < n; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}

			sorted = Arrays.stream(arr)
				.distinct()
				.sorted()
				.toArray();

			for (int j = 0; j < n; j++) {
				zips[i][j] = Arrays.binarySearch(sorted, arr[j]);
			}
		}

		int total = 0;

		for (int i = 0; i < m; i++) {
			for (int j = i + 1; j < m; j++) {
				if (Arrays.equals(zips[i], zips[j])) total++;
			}
		}

		System.out.println(total);
	}
}

문제

접근 방식

주어진 수들에서 중복을 허용하여 3개의 수를 더한 값이

이미 배열에 존재하는 경우 중 가장 큰 값을 찾아야 한다.

수들이 최대 1000개 주어지기 때문에 3중 반복문으로

모든 경우를 다 곱하는 경우만 해도 최대 10억 번의 계산이 필요해

값을 찾기까지 하려면 절대 불가능한 방법이다.

문제를 x + y + z가 아니라 (x + y) + z로 나누어 생각해보면

x + y를 먼저 구해둔 후에 합해서 z가 될 수 있는 경우를 찾으면 된다.

x + y를 모두 구하면 최대 1,000,000개가 나올 수 있기 때문에

이걸 매번 O(N)으로 반복 순회하면 안되고

정렬하여 이분 탐색으로 찾아주면 된다.

정리하면 아래와 같다.

1. 배열을 정렬한다. nums

2. (x + y) 쌍을 구한다. pairs

3. 구한 쌍들도 정렬한다. 

4. 큰 값부터 찾기 위해 기존 배열을 역순으로 순회하며

5. 기존 배열을 원래대로 순회하면서 값을 빼주고 그 값이 구한 쌍에 존재하는지 확인한다.

(pairs에 nums[i] - nums[j]가 존재하는지)

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[] nums = new int[n];
		List<Integer> pairs = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			nums[i] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(nums);

		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				pairs.add(nums[i] + nums[j]);
			}
		}

		Collections.sort(pairs);
		int idx = -1;

		out:
		for (int i = n - 1; i >= 0; i--) {
			for (int j = 0; j < n; j++) {
				if (Collections.binarySearch(pairs, nums[i] - nums[j]) >= 0) {
					idx = i;
					break out;
				}
			}
		}

		System.out.println(nums[idx]);
	}
}

문제

접근 방식

문제 이름 그대로 트리의 높이와 넓이를 구해야 하는데

주의해야 할 점은 이진 트리가 주어질 때 루트 노드는 주어지지 않기 때문에

탐색을 무조건 1번 정점에서 시작하는 것이 아니라

따로 루트 노드를 찾아서 시작해줘야 한다.

트리의 높이야 탐색을 하면서 자식 노드를 방문할 때마다

부모 노드의 높이 + 1을 해주면 되니 쉽게 구할 수 있지만

문제는 트리의 넓이를 구하는 것이다.

위의 트리의 경우를 살펴보면 알 수 있는게 가로 한 줄에는

하나의 정점만 존재할 수 있고, 가장 왼쪽 가로줄의 정점부터 1번째

가장 오른쪽의 정점을 n번째로 방문한다.

즉, 처음 방문하는 정점은 8번 정점일 것이고

가장 마지막에 방문하는 정점은 7번 정점이 된다.

이진 트리가 주어지니 전위, 중위, 후위 순회 중에서 문제에 적합한

방법을 선택해서 탐색하면서 각 계층마다 처음 방문 하는 곳과

가장 나중에 방문하는 곳들을 기록해두기만 하면 된다.

이 문제는 왼쪽부터 가장 처음 탐색하고 중간, 오른쪽 순으로

탐색해야 하기 때문에 중위 순회가 가장 적합하다.

탐색하면서 기록을 하기 위해 계층별로 길이가 2인 2차원 배열에

처음 방문한 경우의 순서와 마지막에 방문한 경우의 순서를 저장하고

탐색이 끝나면 해당 배열을 사용해 이 둘을 뺀 값이 가장 큰 경우가

가장 넓은 구간을 구하는 방법이다. 

풀이

public class Main {

	private static int idx = 1;
	private static int height;
	private static int[] p, lc, rc;
	private static int[][] width;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		int c, l, r;

		p = new int[n + 1];
		lc = new int[n + 1];
		rc = new int[n + 1];
		width = new int[n + 1][2];

		Arrays.fill(p, -1);

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			c = Integer.parseInt(st.nextToken());
			l = Integer.parseInt(st.nextToken());
			r = Integer.parseInt(st.nextToken());

			lc[c] = l;
			rc[c] = r;
			if (l != -1) p[l] = c;
			if (r != -1) p[r] = c;
		}

		int root = 0;

		for (int i = 1; i <= n; i++) {
			if (p[i] == -1) {
				root = i;
				break;
			}
		}

		in(root, 1);

		int maxDepth = 1;
		int maxWidth = 1;

		for (int i = 2; i <= height; i++) {
			int mw = Math.abs(width[i][0] - width[i][1]) + 1;
			if (width[i][0] * width[i][1] == 0) mw = 1;
			if (mw > maxWidth) {
				maxDepth = i;
				maxWidth = mw;
			}
		}

		System.out.println(maxDepth + " " + maxWidth);
	}

	private static void in(int cur, int d) {
		if (lc[cur] != -1) in(lc[cur], d + 1);
		height = Math.max(d, height);
		if (width[d][0] == 0) width[d][0] = idx++;
		else width[d][1] = idx++;
		if (rc[cur] != -1) in(rc[cur], d + 1);
	}
}

문제

접근 방식

내리 칭찬이 있어서 부하는 상사가 받은 칭찬 + 상사한테 받을 칭찬을 받을 수 있다.

트리에서 상사는 부모고 부하는 자식이니 루트부터 방문을 하면서

부하에게 현재까지 본인이 받은 칭찬을 넘겨주기만 하면 된다.

조심해야할게 한 명의 부하가 여러번 칭찬을 받을 수 있어서

입력을 받을 때

부하 번호 = 부하가 직속 상사로부터 받은 칭찬 이 아니라

부하 번호 += 부하가 직속 상사로부터 받은 칭찬 이 되어야 한다.

풀이

public class Main {

	private static final ArrayList<ArrayList<Integer>> near = new ArrayList<>();
	private static int[] compliments;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int p;
		compliments = new int[n + 1];

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		st = new StringTokenizer(br.readLine());

		for (int i = 1; i <= n; i++) {
			p = Integer.parseInt(st.nextToken());
			if (p == -1) continue;

			near.get(p).add(i);
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			compliments[Integer.parseInt(st.nextToken())] += Integer.parseInt(st.nextToken());
		}

		dfs(1);

		for (int i = 1; i <= n; i++) {
			sb.append(compliments[i]).append(" ");
		}

		System.out.println(sb);
	}

	private static void dfs(int cur) {
		for (int next : near.get(cur)) {
			compliments[next] += compliments[cur];
			dfs(next);
		}
	}
}

문제

접근 방식

분리 집합과 유니온 파인드에 대해서 아직 배우지 않아

기존에 풀었던 4803번 문제와 비슷하게 풀면 풀 수 있겠다 생각이 들어

무작정 시도해봤는데 어찌저찌 풀었다.

우선 이번 문제는 그래프가 주어졌을 때

간선을 지우거나 추가하여 하나의 트리로 만들기 위한

총 횟수를 구해야 한다.

간단하게 생각하면

한 정점에서 방문할 수 있는 모든 정점을 방문했을 때

사이클이 존재하지 않는다면 이미 하나의 트리니

기존의 트리와 합치기만 하면 될 것이고

그렇지 않다면 간선을 제거해주고 합쳐주면 된다.

사이클이 존재하는 경우에 몇 개의 간선을 제거해야 하는지는

트리의 규칙을 생각해보면 쉬운데

정점 N개의 트리는 N-1개의 간선을 가지고 있으니

현재까지 발견한 간선의 수 - (N - 1) = 삭제해야 할 간선의 수

라는 것을 알 수 있다.

발그림으로나마 더 쉽게 설명하자면

위와 같이 그래프가 주어졌을 때,

1-2-3은 이미 트리니 그대로 두고

4-5-6-7은 간선의 개수가 N-1보다 하나 더 많으니

간선을 하나 잘라주고

8-9-10-11도 이미 트리니 그대로 두면 된다.

이제 세 트리를 위와 같이 서로 이어주면 되는데

이 경우도 마찬가지로, 각각의 트리를 정점이라 생각했을 때 

N-1개 만큼 간선을 추가해주면 된다.

풀이

public class Main {

	private static int node, edge;
	private static boolean[] isVisited;
	private static final ArrayList<ArrayList<Integer>> near = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		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 x, y;
		int cut = 0;
		int tree = 0;

		isVisited = new boolean[n + 1];

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());

			near.get(x).add(y);
			near.get(y).add(x);
		}

		for (int i = 1; i <= n; i++) {
			if (isVisited[i]) continue;
			tree++;
			node = edge = 0;
			dfs(i);
			if (edge != (node - 1) * 2) {
				cut += (edge - ((node - 1) * 2))/2;
			}
		}

		System.out.println(cut + tree - 1);
	}

	private static void dfs(int cur) {
		isVisited[cur] = true;
		node++;

		for (int next : near.get(cur)) {
			edge++;
			if (isVisited[next]) continue;
			dfs(next);
		}
	}
}

문제

접근 방식

이전까지의 트리 문제에서는 각 노드 간의 거리가 1이였다면

이번 문제에서는 노드 간 거리가 서로 다르게 주어진다.

그래서 인접 리스트를 만들 때

기존에는 각 각선의 양끝 정점에 대해서만 넣어줬다면

이번에는 정점 간의 거리도 넣어준 후에 탐색만 해주면 된다.

풀이

public class Main {

	private static int start, end, result;
	private static boolean[] isVisited;
	private static final ArrayList<ArrayList<Pair>> near = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int x, y, d;

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		for (int i = 1; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			d = Integer.parseInt(st.nextToken());

			near.get(x).add(new Pair(y, d));
			near.get(y).add(new Pair(x, d));
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			isVisited = new boolean[n + 1];

			dfs(start, 0);
			sb.append(result).append("\n");
		}

		System.out.println(sb);
	}

	private static void dfs(int cur, int move) {
		isVisited[cur] = true;

		for (Pair pair : near.get(cur)) {
			if (isVisited[pair.node]) continue;
			if (pair.node == end) {
				result = move + pair.dist;
				return;
			}
			dfs(pair.node, move + pair.dist);
		}
	}

	private static class Pair {
		int node;
		int dist;

		public Pair(int node, int dist) {
			this.node = node;
			this.dist = dist;
		}
	}
}

문제

접근 방식

정점이 N개이고 루트가 R인 올바른 트리에 대한 간선이 주어졌을 때

정점이 U인 경우에는 몇 개의 정점을 방문할 수 있는지를 알아내면 된다.

예를 들어 위와 같은 트리가 있을 때를 생각해보면

루트인 5번 정점부터 방문하면 당연히 모든 정점인

9개의 정점을 다 방문할 수 있다.

하지만 4번 정점부터 방문한다면 위와 같이 4개의 정점만 방문할 것이고

8번 정점부터 방문한다면 8번 하나만 방문할 수 있다.

이제 특정 정점에 포함된 정점의 개수가 몇 개인지를 알아내면 되는데

이는 트리의 성질을 이용하면 쉽게 계산할 수 있다.

위의 트리를 다시 살펴보면

정점 3의 경우는 자기 자신을 포함한 자식 노드의 정점 수의 합인 3이고

정점 4의 경우도 마찬가지로 자기 자신을 포함한 자식 노드인 3번 노드의

정점 수의 합인 4가 되고, 5번 정점도 마찬가지로 자기 자신 + 4번 + 6번이 된다.

즉, 탐색하면서 부모 노드에 자식 노드들을 더해주면 각 노드에 포함된

모든 정점의 개수를 알 수 있고, 쿼리마다 탐색을 하지 않아도

한 번의 탐색으로 처리할 수 있다.

풀이

public class Main {

	private static final ArrayList<ArrayList<Integer>> near = new ArrayList<>();
	private static int[] counts;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		int x, y;

		counts = new int[n + 1];

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		for (int i = 1; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());

			near.get(x).add(y);
			near.get(y).add(x);
		}

		travel(r);

		while (q-- > 0) {
			sb.append(counts[Integer.parseInt(br.readLine())]).append("\n");
		}

		System.out.println(sb);
	}

	private static void travel(int cur) {
		counts[cur] = 1;

		for (int next : near.get(cur)) {
			if (counts[next] != 0) continue;
			travel(next);
			counts[cur] += counts[next];
		}
	}
}