da9dac

문제

접근 방식

가장 많은 양의 포도주를 마실 수 있는 경우를 찾아야 하는데

두 번째 조건을 보면 연속으로 마실 수 있는 포도주는 두 잔까지고

이는 1,2번째 잔을 마셨다면 3번째 잔은 건너뛰고

4,5,6,...n번째 포도주 중 하나를 먹어야 한다는 말이다.

거꾸로 생각해 보면 두 잔을 연속으로 마실 때는 이전 잔을 무조건 마셨다는 것이 되고

한 잔만 마셨을 때는 바로 이전 잔을 제외한 이전의 어떠한 잔들 중 하나 이상은 마신 것이 된다.

만약 n번째 잔을 마실 때, 해당 잔이 연속으로 두 번째 마시고 있는 잔이라면

(n번 잔의 양 + n-1번 잔을 첫 번째로 마신 경우의 최댓값) 이 해당 경우의 최댓값이 되고

해당 잔이 연속이 아닌 첫 번째로 마시고 있는 잔이라면

n-2 이하 번의 잔의 최댓값 + n번 잔의 양이 최댓값이 된다.

점화식을 정리하면 다음과 같다.

dp[n][한 잔을 연속으로 마신 경우] = dp[n-2][누적 최댓값] + n번 잔의 양
dp[n][두 잔을 연속으로 마신 경우] = dp[n-1][한 잔을 연속으로 마신 경우] + n번 잔의 양
dp[n][누적 최댓값] = max(dp[n-1][누적 최댓값], dp[n][한 잔을 연속으로 마신 경우], dp[n][두 잔을 연속으로 마신 경우])

풀이

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[] cups = new int[n + 1];
        int[][] dp = new int[n + 1][3];

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

        dp[1][0] = cups[1];
        dp[1][2] = cups[1];

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

        System.out.println(dp[n][2]);
    }
}

문제

접근 방식

한 자리의 경우 : 1
두 자리의 경우 : 11, 00
세 자리의 경우 : 111, 100, 001
네 자리의 경우 : 1111, 1100, 1001, 0011, 0000
다섯 자리의 경우 : 11111, 11100, 11001, 10011, 10000, 00111, 00100, 00001

각 자릿수 별로 경우의 수를 적어보면 위와 같다.

우리가 사용할 수 있는 숫자는 한 자리인 1과 두 자리인 00 두 가지만 있는데

만약 여섯 자리의 수를 만들어야 한다 가정하면

첫자리에 1이 오면 그 뒤에는 다섯 자리의 수가 올 수 있을 테니

기존에 구해둔 다섯 자리의 경우만큼 만들 수 있을 것이고

첫자리에 00이 오면 그 뒤에는 네 자리의 수가 올 수 있으니

기존에 구해둔 네 자리의 경우만큼 만들 수 있을 것이다.

결국 1로 시작하는 경우와 00으로 시작하는 경우를 합쳐주면

n자리의 수를 만들 수 있는 경우의 수를 구할 수 있다.

점화식을 정리하면

첫자리에 1이 오는 경우는 (n-1)자리의 경우의 수가 되고

첫 자리에 00이 오는 경우는 (n-2)자리의 경우의 수가 되니

f(n) = f(n-1) + f(n-2) 가 된다.

풀이

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[] arr = new int[1000001];

        arr[1] = 1;
        arr[2] = 2;

        for (int i = 3; i <= n; i++) arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;

        System.out.println(arr[n]);
    }
}

문제

접근 방식

가장 낮은 값과 (다음으로 낮은 값 * 2)을 더한 값을 다시 포함하여

모든 수가 K 이상이 되게 만들어야 한다.

즉, 가장 낮은 값 두 개를 뺀 후에 섞고 다시 섞은 것을 추가해야 하고

이 때, 항상 정렬된 상태를 유지해야 하는게 중요하다.

섞은 것을 추가할 때마다 정렬을 하기에는 시간 복잡도가 비효율적이기 때문에

값이 추가되어도 항상 정렬된 상태를 유지할 수 있는 우선순위 큐를 사용하면 쉽다.

처음에는 우선순위 큐에 모든 값들을 넣어주고

큐에서 가장 작은 값을 두 개씩 빼가며 섞어주고 다시 넣어주다가

꺼낸 값이 K 이상이라면 이후의 값들도 당연히 K 이상이기 때문에

현재까지의 카운트를 리턴해주면 되고

값을 하나 꺼냈는데 더 이상 남은 것이 없다면 더 이상 섞을 것이 없기 때문에

모든 값을 K 이상으로 만들 수 없다는 것이 되어 -1을 출력해준다.

풀이

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        
        for (int s : scoville) q.offer(s);
        
        int cnt = 0;
        
        while(!q.isEmpty()) {
            int first = q.poll();
            
            if(first >= K) break;
            if(q.isEmpty()) return -1;
            
            cnt++;
            
            q.offer(first + (q.poll() * 2));
        }
        
        return cnt;
    }
}

문제

접근 방식

별 찍기 문제들은 재귀 처음 배울 때 너무 싫어했던 기억이 있어서

풀기 싫었는데 스트릭 유지할겸 오랜만에 재귀 문제를 풀어보았다.

정사각형이 점점 작아지는 형태로

예를 들면 가장 밖의 정사각형이 13 * 13이라면

그 안의 사각형은 상하좌우 한 칸 거리를 두고 9 * 9

그 안의 사각형도 상하좌우 한 칸 거리를 두고 5 * 5

마지막은 1 * 1이 된다.

규칙을 찾아보면 사각형의 가로세로 길이가 4씩 줄어드는 것을 알 수 있는데

재귀를 호출할 때마다 x축과 y축을 4씩 늘리거나 줄여주면서

2차원 문자 배열에 별을 저장한 후에 모두 끝나면 배열을 출력해주면 된다.

풀이

public class Main {

	private static char[][] stars;

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

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

		stars = new char[1 + (n - 1) * 4][1 + (n - 1) * 4];

		star(0, 1 + (n - 1) * 4);

		for (char[] star : stars) {
			sb.append(star).append("\n");
		}

		System.out.println(sb);
	}

	private static void star(int x, int y) {

		if (x >= y) return;

		for (int i = x; i < y; i++) {
			if (i == x || i == y - 1) {
				for (int j = x; j < y; j++) stars[i][j] = '*';
			} else {
				stars[i][x] = '*';
				for (int j = x + 1; j < y - 1; j++) stars[i][j] = ' ';
				stars[i][y - 1] = '*';
			}
		}

		star(x + 2, y - 2);
	}
}

문제

접근 방식

문제에 적힌거처럼 위 함수를 그대로 구현하고 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++;
	}
}