99클럽 코테 스터디 17일차 TIL

비기너

문제

25497번: 기술 연계마스터 임스

# 스택

https://www.acmicpc.net/problem/25497

풀이

n개의 기술이 주어졌을 때 기술을 사용한 총 횟수를 구하는 문제이다.

연계기술의 발동을 체크하는 것이 포인트인데  연계기술은 L-R과 S-K 두 가지가 있다.

두 연계 기술의 발동을 체크하기 위해서 스택 두 개를 사용해서 연계 기술의 사전기술이 나오면 각각의 스택에 담는다.

본 기술이 나오면 각각의 스택을 체크해서 사전기술이 발동한 적이 있는지 확인한다.

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		String s = br.readLine();
		Stack<Character> st1 = new Stack<>();
		Stack<Character> st2 = new Stack<>();

		int ans = 0;
		for (char c : s.toCharArray()) {
			if (c >= '1' && c <= '9')
				ans++;
			else if (c == 'S')
				st1.push(c);
			else if (c == 'L')
				st2.push(c);
			else if (c == 'K' && !st1.empty() && st1.peek() == 'S') {
				st1.pop();
				ans++;
			} else if (c == 'R' && !st2.empty() && st2.peek() == 'L') {
				st2.pop();
				ans++;
			} else
				break;
		}

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

미들러

문제

31926번: 밤양갱

# 그리디

https://www.acmicpc.net/problem/31926

풀이

n개의 daldidalgo와 1개의 daldidan으로 구성된 문자열을 입력할 때 입력할 수 있는 최소 시간을 구하는 문제이다.

우선 첫 daldidalgo를 입력할 때 필요한 시간은 8초이다. (d, a, l, d, i, dal, g, o)

또한 마지막 daldidan을 입력할 때 필요한 시간은 2초이다. (daldida, n)

daldidalgo를 복사할 때마다 한 번에 복사 붙여넣기할 수 있는 수가 2의 거듭제곱으로 증가한다.

따라서 (2^(k-1), 2^k] 사이에 n이 포함되면 k번의 입력을 통해 n -1개의 daldidalgo를 입력할 수 있다.

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int ans = 10;
		int tmp = 2;
		int cnt = 0;
		while (tmp <= n) {
			tmp *= 2;
			cnt++;
		}
		ans += cnt;

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

2056번: 작업

# 위상정렬

https://www.acmicpc.net/problem/2056

풀이

작업 간의 선행관계가 주어질 때 모든 작업을 완료하기 위한 최소 시간을 출력하는 문제이다.

즉 모든 작업이 끝나는 시간을 구하고 그 중 최댓값을 구해주면 된다.

작업들 간의 선행관계를 그래프로 나타낼 수 있으므로 위상정렬을 이용하면 모든 작업의 끝나는 시간을 구할 수 있다.

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] a = new int[n + 1];
		int[] cnt = new int[n + 1];
		int[] ans = new int[n + 1];
		ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
		for (int i = 0; i <= n; i++)
			adj.add(new ArrayList<>());

		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			a[i] = Integer.parseInt(st.nextToken());
			ans[i] = a[i];
			cnt[i] = Integer.parseInt(st.nextToken());
			if (cnt[i] == 0)
				q.add(i);
			for (int j = 0; j < cnt[i]; j++) {
				int x = Integer.parseInt(st.nextToken());
				adj.get(x).add(i);
			}
		}

		while (!q.isEmpty()) {
			int x = q.poll();
			for (int nx : adj.get(x)) {
				cnt[nx]--;
				ans[nx] = Math.max(ans[nx], ans[x] + a[nx]);
				if (cnt[nx] == 0)
					q.add(nx);
			}
		}

		int tmp = 0;
		for (int i = 1; i <= n; i++)
			tmp = Math.max(tmp, ans[i]);

		bw.write(tmp + "");
		bw.flush();
		bw.close();
	}
}