da9dac

문제

접근 방식

처음에는 이름이랑 그림만 보고 트리 문제인가 했는데 읽고서 그림을 그려보다 보니 DP 문제에 가까워 보였다.

근데 막상 DP를 사용해서 풀지도 않았고 이게 왜 티어를 골드 4까지나 준건지 모르겠는 문제인데, 규칙만 찾으면 코드 몇 줄로도 간단하게 풀 수 있다.

아래에서부터 왼중오 3개의 노드를 하나의 차로 방문하는 것이 가장 적은 차를 사용하는 경우이고, 주어진 입력내 트리의 노드 수가 long의 범위를 벗어나지 않기 때문에 DP를 사용하지 않고도 단순 연산으로도 풀 수 있다.

풀이

public class Main {

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

		int h = Integer.parseInt(br.readLine());

		long road = (2L << h) - 1;

		long result = road % 3 != 0 ? road / 3 + 1 : road / 3;

		System.out.println(result);
	}
}

문제

접근 방식

인접 리스트를 만든 후에 일반적인 그래프 탐색으로 여행 경로를 모두 이동해보면

시간 초과가 발생하기 때문에 여행 경로가 모두 한 사이클에 포함 되는지만 파악하면 된다.

이럴 때 효율적인 알고리즘이 유니온 파인드인데

유니온 함수를 이용해 연결된 정점들끼리의 부모를 기록해두고

파인드 함수를 이용해 서로의 최고 조상이 누구인지 확인하여

같은 사이클에 존재하는지 여부를 빠르게 판단할 수 있다.

초기에는 각 도시마다 자기 자신을 부모로 초기화하고

주어진 도시 간의 경로를 유니온 함수로 연결한 후에

여행 경로대로 파인드 함수를 사용해 모두 하나의 사이클에 포함되는지 확인한다.

풀이

public class Main {

	static int[] parent;

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

		boolean isPossible = true;
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		parent = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		}

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

			for (int j = 1; j <= n; j++) {
				if (Integer.parseInt(st.nextToken()) == 0) continue;
				union(i, j);
			}
		}

		st = new StringTokenizer(br.readLine());
		int x = find(Integer.parseInt(st.nextToken()));

		for (int i = 1; i < m; i++) {
			if (find(Integer.parseInt(st.nextToken())) != x) {
				isPossible = false;
				break;
			}
		}

		System.out.println(isPossible ? "YES" : "NO");
	}

	static void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x != y) parent[y] = x;
	}

	static int find(int x) {
		if (parent[x] == x) return x;
		return parent[x] = find(parent[x]);
	}
}

문제

접근 방식

그래프 문제도 아니고 그냥 일반적인 반복문 문제라

입력 받고 8방향 중 한 방향으로 4개의 알파벳들이 각각 O B I S인지 모두 확인해주면 된다.

문자 배열을 미리 만들어두고 비교를 했는데 목표 단어에 중복된 문자가 존재하지 않아서

애초에 M을 1, O를 2, ..., S를 5로 두고 증가하는 순으로 비교하면 더 깔끔할거 같다.

풀이

public class Main {

	static int n, cnt = 0;
	static char[] chars = new char[]{'O', 'B', 'I', 'S'};
	static char[][] map;
	static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

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

		n = Integer.parseInt(br.readLine());
		map = new char[n][n];
		Queue<Pair> q = new LinkedList<>();

		for (int i = 0; i < n; i++) {
			String str = br.readLine();

			for (int j = 0; j < n; j++) {
				char c = str.charAt(j);
				map[i][j] = c;
				if (c == 'M') q.offer(new Pair(i, j));
			}
		}

		while (!q.isEmpty()) {
			Pair cur = q.poll();

			for (int dir = 0; dir < 8; dir++) {
				int nx = cur.x + dx[dir] * 4;
				int ny = cur.y + dy[dir] * 4;

				if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

				int x = cur.x + dx[dir];
				int y = cur.y + dy[dir];

				for (int i = 0; i < 4; i++) {
					if (map[x][y] != chars[i]) break;
					x += dx[dir];
					y += dy[dir];
					if (i == 3) cnt++;
				}
			}
		}

		System.out.println(cnt);
	}


	static class Pair {
		int x, y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

문제

접근 방식

문제가 너무 대놓고 그래프로 네 방향을 탐색하라고 나와 있는데 이거에 낚이면 시간초과에 걸린다.

장애물이 없는 지도가 주어져서 현재 지점의 좌표와 이동하고자 하는 지점의 좌표의 차를 구하면

몇 칸을 이동해야하는지 알 수 있기 때문에 직접 한 칸씩 움직일 필요가 없다.

그래서 집의 좌표와 민초우유의 좌표만 구해두고 집의 위치에서부터 시작해서

현재 좌표와 민초우유의 좌표의 차를 구하고 현재 체력보다 작거나 같다면 이동해주면 된다.

풀이

public class Main {

	static int n, m, h, max = 0, milk = 0;
	static Pair home;
	static ArrayList<Pair> milks = new ArrayList<>();
	static boolean[] isVisited;

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

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

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

			for (int j = 0; j < n; j++) {
				int x = Integer.parseInt(st.nextToken());

				if (x == 1) {
					home = new Pair(i, j);
				} else if (x == 2) {
					milks.add(new Pair(i, j));
					milk++;
				}
			}
		}

		isVisited = new boolean[milk];

		solve(home.x, home.y, 0);

		System.out.println(max);
	}

	static void solve(int x, int y, int eat) {
		for (int i = 0; i < milk; i++) {
			if (isVisited[i]) continue;

			isVisited[i] = true;

			Pair pair = milks.get(i);

			int nx = pair.x;
			int ny = pair.y;
			int distNext = getDist(x, y, nx, ny);

			if (distNext <= m) {
				m += h;
				m -= distNext;
				if (getDist(home.x, home.y, nx, ny) <= m) max = Math.max(max, eat + 1);
				solve(nx, ny, eat + 1);
				m -= h;
				m += distNext;
			}

			isVisited[i] = false;
		}
	}

	static int getDist(int ax, int ay, int bx, int by) {
		return Math.abs(ax - bx) + Math.abs(ay - by);
	}

	static class Pair {
		int x, y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

문제

접근 방식

여러 풀이가 존재하는 문제 같지만 BFS를 사용해서 풀어봤다.

우선 문제에서는 10*10 맵이라고 했지만 그냥 100칸짜리 1차원 배열을 사용하는 것이

문제의 입력 양식을 처리하기가 편해서 맵과 방문 배열을 모두 1차원 배열을 사용했다.

평범한 BFS 문제와 방식은 비슷하지만 주사위의 눈만큼 이동하기 위해

방향 배열을 사용하는 것이 아닌 1 ~ 6까지 반복문을 돌아주었다.

사다리나 뱀은 무조건 타야 하기 때문에 이 부분만 주의하면서 탐색해 주고

방문 기록을 정수형 배열로 처리해 주사위를 굴린 횟수가 더 적은 경우에만

이동할 수 있게 해 주면 된다.

풀이

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[] map = new int[101];
		int[] isVisited = new int[101];
		Arrays.fill(isVisited, -1);

		int nm = Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken());

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

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

			map[x] = y;
		}

		Queue<Integer> q = new ArrayDeque<>();
		q.offer(1);
		isVisited[1] = 0;

		while (!q.isEmpty()) {
			int cur = q.poll();
			int move = isVisited[cur] + 1;

			for (int dice = 1; dice <= 6; dice++) {
				int next = cur + dice;

				if (next > 100) continue;

				if (map[next] != 0) {
					int x = map[next];

					if (isVisited[x] != -1 && isVisited[x] <= move) continue;

					isVisited[x] = move;
					q.offer(x);

					continue;
				}

				if (next == 100) {
					System.out.println(move);
					return;
				}

				if (isVisited[next] != -1 && isVisited[next] <= move) continue;

				isVisited[next] = move;
				q.offer(next);
			}
		}
	}
}

문제

접근 방식

바이토닉 수열인 오름차순, 내림차순, 오름차순 + 내림차순 수열 중 가장 긴 것을 찾아야 한다.

이전에 풀었던 문제 중 가장 긴 증가하는 부분 수열을 응용하면 풀 수 있는 문제인데

v		v			v	v	v
1	5	2	1	4	3	4	5	2	1

만약에 위와 같은 수열이 있다면 1, 2, 3, 4, 5가 가장 긴 증가하는 부분 수열일 것이고

	v			v	v			v	v
1	5	2	1	4	3	4	5	2	1

가장 긴 감소하는 부분 수열은 위와 같을 것이다.

가장 긴 증가하는 부분 수열과 감소하는 부분 수열의 길이를 표로 정리하면 다음과 같다.

1	5	2	1	4	3	4	5	2	1

1	2	2	1	3	3	4	5	2	1
1	5	2	1	4	3	3	3	2	1

이렇게 표를 정리하고 나면 같은 값에 해당하는 길이끼리 합치면

오름차순과 내림차순이 합쳐진 바이토닉 부분 수열을 만들 수 있는 것을 알 수 있다.

예를 들어 길이가 5인 증가하는 부분 수열과 3인 감소하는 부분 수열을 합치면

1, 2, 3, 4, 5 + 5, 2, 1 = 1, 2, 3, 4, 5, 5, 2, 1 만들어질 것이고

5는 겹치는 부분이니 총개수의 합인 8에서 1을 빼주면 된다.

정리하면 두 경우의 부분 수열의 길이를 구해서 합한 후에 가장 큰 값을 구해주면 된다.

풀이

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 max = 0;
		int[] arr = new int[n];
		int[] dp = new int[n];
		int[] dpr = new int[n];

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

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

			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}

		for (int i = n - 1; i >= 0; i--) {
			dpr[i] = 1;

			for (int j = n - 1; j > i; j--) {
				if (arr[j] < arr[i]) {
					dpr[i] = Math.max(dpr[i], dpr[j] + 1);
				}
			}

			dp[i] += (dpr[i] - 1);
			max = Math.max(dp[i], max);
		}

		System.out.println(max);
	}
}

문제

접근 방식

노드 간의 거리가 모두 1로 동일할 때, 시작점 X에서 거리가 K인 정점을 출력해야 한다.

즉 탐색은 X에서 K번 까지의 이동만 진행해주면 되고, K번째 방문한 정점들을 모두 저장해주면 되는데

문제에서 요구하는 출력값이 정점의 번호를 오름차순으로 출력하는 것이기 때문에

트리셋이나 우선순위큐, 정렬 등을 사용해서 출력해주면 된다.

풀이

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());
		StringBuilder sb = new StringBuilder();

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

		int[] isVisited = new int[n + 1];
		Arrays.fill(isVisited, -1);

		ArrayList<ArrayList<Integer>> near = new ArrayList<>();
		TreeSet<Integer> result = new TreeSet<>();

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

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

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

			near.get(a).add(b);
		}

		Queue<Integer> q = new ArrayDeque<>();

		q.offer(x);
		isVisited[x] = 0;

		while (!q.isEmpty()) {
			int cur = q.poll();

			for (int next : near.get(cur)) {
				if (isVisited[next] != -1) continue;
				isVisited[next] = isVisited[cur] + 1;
				if (isVisited[next] == k) {
					result.add(next);
					continue;
				} else if (isVisited[next] > k) {
					continue;
				}
				q.offer(next);
			}
		}

		if (result.isEmpty()) {
			sb.append(-1);
		} else {
			for (int i : result) {
				sb.append(i).append("\n");
			}
		}

		System.out.println(sb);
	}
}

문제

접근 방식

m	v
1	65
2	98
2	95
5	99
5	96
5	90

보석의 무게와 가치를 위와 같이 무게가 가벼운 순으로, 같다면 가치가 높은 순으로 정렬한 후에

오름차순으로 정렬된 가방을 하나씩 보면서 현재 가방의 무게 이하인 보석을 모두 우선순위 큐에 넣고

가장 큰 값을 하나만 꺼내서 누적합에 더해주면 된다.

2
2
10
10

가방의 무게가 다음과 같을 때

[2]	98 95 65
[2]	95 65
[10]	99 96 90 65
[10]	96 90 65

처음 가방 무게가 2일 때는 98, 95, 65를 추가하고 그중에서 가장 큰 98을 큐에서 꺼내고

다음 가방 무게가 2일 때도 남은 95, 65 중에서 95를 꺼낸 후에

가방 무게가 10일 때 99와 90을 추가한 후에 가장 큰 99를 꺼내고

마지막 가방 무게가 10일 때 남은 96, 90, 65 중에서 가장 큰 96을 꺼낸다.

풀이

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 n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		long max = 0;

		PriorityQueue<Gem> gems = new PriorityQueue<>();
		PriorityQueue<Integer> bags = new PriorityQueue<>();
		PriorityQueue<Integer> values = new PriorityQueue<>(Comparator.reverseOrder());

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

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

			gems.offer(new Gem(m, v));
		}

		for (int i = 0; i < k; i++) {
			int c = Integer.parseInt(br.readLine());
			bags.offer(c);
		}

		while (!bags.isEmpty()) {
			int bag = bags.poll();

			while (!gems.isEmpty()) {
				Gem gem = gems.peek();

				if (gem.m > bag) break;

				gems.poll();
				values.offer(gem.v);
			}

			if (!values.isEmpty()) max += values.poll();
		}

		System.out.println(max);
	}

	static class Gem implements Comparable<Gem> {
		int m, v;

		Gem(int m, int v) {
			this.m = m;
			this.v = v;
		}

		@Override
		public int compareTo(Gem o) {
			return this.m != o.m ? this.m - o.m : o.v - this.v;
		}
	}
}