da9dac

문제

접근 방식

문제에 적힌거처럼 위 함수를 그대로 구현하고 15, 15, 15 이상의 값들을 넘겨주면

재귀의 깊이가 너무 깊어져 시간 초과가 발생한다.

중복된 호출을 계속해서 반복하기 때문인데

이러한 문제를 해결하기 위해서는 간단하게 중복된 호출을 하지 않으면 되고

이를 해결하는 방법은 DP와 메모이제이션이 있고

이번에는 메모이제이션을 사용해서 풀어보겠다.

우선 입력의 범위가 -50부터 50까지이기 때문에

배열을 101칸 만들고 50씩 더해서 인덱스를 계산해줄까 생각했는데

문제의 코드를 보고 나니 어차피 1이상 20이하까지만 계산하기 때문에

그 외의 값들을 처리해줄 필요가 없다.

그래서 계산 결과를 처리해줄 3차원 배열을 각 21칸씩 만들어

a, b, c의 경우의 수마다 값을 저장해주면 된다.

이후 함수를 호출할 때마다 이미 저장된 값이 있으면

저장된 값을 리턴하고 그렇지 않은 경우에만

함수를 호출해 값을 배열에 저장해주면

중복된 계산을 피할 수 있다.

DP로 푸는 방법도 간단하게 설명만 하자면

똑같이 3차원 배열을 만든 후에

a, b, c가 각각 0이하인 경우를 모두 1로 채워주고

나머지도 문제의 코드의 조건식대로 값을 채워주면 된다.

풀이

public class Main {

	private static int[][][] dp = new int[21][21][21];

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

		while (true) {
			st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			if (a == -1 && b == -1 && c == -1) break;

			sb.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ");

			sb.append(w(a, b, c)).append("\n");
		}

		System.out.println(sb);
	}

	private static int w(int a, int b, int c) {
		if (a <= 0 || b <= 0 || c <= 0) return 1;

		if (a > 20 || b > 20 || c > 20) {
			if (dp[20][20][20] == 0) dp[20][20][20] = w(20, 20, 20);
			return dp[20][20][20];
		}

		if (a < b && b < c) {
			dp[a][b][c-1] = dp[a][b][c-1] != 0 ? dp[a][b][c-1] : w(a, b, c - 1);
			dp[a][b-1][c-1] = dp[a][b-1][c-1] != 0 ? dp[a][b-1][c-1] : w(a, b - 1, c - 1);
			dp[a][b-1][c] = dp[a][b-1][c] != 0 ? dp[a][b-1][c] : w(a, b - 1, c);
			return dp[a][b][c-1] + dp[a][b-1][c-1] - dp[a][b-1][c];
		}

		dp[a-1][b][c] = dp[a-1][b][c] != 0 ? dp[a-1][b][c] : w(a - 1, b, c);
		dp[a-1][b-1][c] = dp[a-1][b-1][c] != 0 ? dp[a-1][b-1][c] : w(a - 1, b - 1, c);
		dp[a-1][b][c-1] = dp[a-1][b][c-1] != 0 ? dp[a-1][b][c-1] : w(a - 1, b, c - 1);
		dp[a-1][b-1][c-1] = dp[a-1][b-1][c-1] != 0 ? dp[a-1][b-1][c-1] : w(a - 1, b - 1, c - 1);

		return dp[a-1][b][c] + dp[a-1][b-1][c] + dp[a-1][b][c-1] - dp[a-1][b-1][c-1];
	}
}

문제

접근 방식

기본적인 재귀 문제로 문제에 기저 조건부터 규칙까지 그대로 나와 있기 때문에

코드로 구현만 하면된다.

우선 재귀 함수의 기저 조건은 선의 길이가 1일 때일 것이고

현재 선의 중앙을 길이의 3분의 1만큼 공백으로 바꿔준 후에

나머지 왼쪽과 오른쪽 선도 재귀를 이용해 같은 과정을 반복해주면 된다.

풀이

public class Main {

	private static char[] chars;

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

		String input;

		while ((input = br.readLine()) != null) {
			int n = Integer.parseInt(input);
			int len = (int) Math.pow(3, n);

			chars = new char[len];

			for (int i = 0; i < len; i++) {
				chars[i] = '-';
			}

			solve(0, len);

			sb.append(chars).append("\n");
		}

		System.out.println(sb);
	}

	private static void solve(int s, int e) {
		if (e - s <= 1) return;

		int x = (e - s) / 3;

		for (int i = s + x; i < e - x; i++) {
			chars[i] = ' ';
		}

		solve(s, s + x);
		solve(e - x, e);
	}
}

문제

접근 방식

Merge Sort를 구현하여 k번째로 정렬되는 수를 구하면 된다.

정렬 후에 k번째 수를 구하는 것이 아닌 정렬 과정에서의 k번째 수인 것에 유의해야 한다.

문제에서 요구하는 구현 방식은 바텀업이 아닌 탑다운 방식이기 때문에

주어진 의사코드대로 구현하면서 카운팅을 해주다 k번째일 때 수를 기록만 하면 된다.

바텀업 방식은 정렬 순서가 조금 다르기 때문에 정렬 결과는 같더라도

해당 문제를 풀기에는 적합하지 않다.

우선 0번째 인덱스부터 n-1번째 인덱스를 정렬하기 위해서는

왼쪽과 오른쪽 절반으로 나누어가면서 더 이상 나눌 수 없을 때까지 나눈 후에

다시 배열을 합쳐가면서 더 작은 값들을 임시 배열에 기록한 후에

임시 배열의 결과를 원본 배열에 옮겨주면 된다.

풀이

public class Main {

	static int cnt = 0, k, result = -1;
	static int[] arr, tmp;

	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());
		k = Integer.parseInt(st.nextToken());

		arr = new int[n];
		tmp = new int[n];

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

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

		sort(0, n - 1);

		System.out.println(result);
	}

	static void sort(int start, int end) {
		if (cnt == k) return;
		if (start < end) {
			int mid = (start + end) / 2;

			sort(start, mid);
			sort(mid + 1, end);
			merge(start, mid, end);
		}
	}

	static void merge(int start, int mid, int end) {
		int i = start;
		int j = mid + 1;
		int idx = 0;

		while (i <= mid && j <= end) {
			if (arr[i] <= arr[j]) tmp[idx++] = arr[i++];
			else tmp[idx++] = arr[j++];
		}

		while (i <= mid) tmp[idx++] = arr[i++];
		while (j <= end) tmp[idx++] = arr[j++];

		i = start;
		idx = 0;

		while (i <= end) {
			cnt++;

			if (cnt == k) {
				result = tmp[idx];
				break;
			}

			arr[i++] = tmp[idx++];
		}
	}
}

문제

접근 방식

트리를 순회하면서 해당 노드에 자식이 없다면

해당 노드는 리프 노드라는 것을 알 수 있으니

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

처음에는 루트 노드가 무조건 0번인줄 알고 풀었는데 틀려서

찾아 보니 루트 노드는 랜덤이기 때문에 이 부분만 조심해서

입력으로 -1을 받을 때 해당 부분을 루트 노드로 지정하고 탐색해주면 된다.

또한 이진 트리가 아닌 일반적인 트리이기 때문에

자식이 꼭 최대 두 개가 아니라 이상일 수도 있다.

풀이

public class Main {

	private static int remove, leaf = 0;
	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));

		int root = 0;
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		remove = Integer.parseInt(br.readLine());

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

		for (int i = 0; i < n; i++) {
			int p = Integer.parseInt(st.nextToken());
			if (p == -1) {
				root = i;
				continue;
			}
			near.get(p).add(i);
		}

		if (remove == root) {
			System.out.println(0);
			return;
		}

		dfs(root);

		System.out.println(leaf);
	}

	private static void dfs(int cur) {
		int size = near.get(cur).size();

		for (int next : near.get(cur)) {
			if (next == remove) {
				size--;
				continue;
			}
			dfs(next);
		}

		if (size == 0) leaf++;
	}
}

문제

접근 방식

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

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

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);
	}
}