공부 기록

N의 범위는 10^9-1 까지이므로 8자리까지 들어올 수 있다.

가장 큰 수가 들어오는 경우를 생각해도 8자리를 3가지 뽑는 경우는 8C3 = 56가지이고,

재귀 함수의 깊이는 그렇게 깊지 않으므로 dp를 사용하지 않아도 될 것이라고 생각했다.

풀다가 한 가지 실수해서 테스트케이스에 걸린 부분이 있는데,

length 를 구할 때, 아무 생각 없이 Math.ceil로 구해버렸다가 테스트케이스 100 이 들어오면 length = 2가 되어버린다는 것을 깨달았다...

고친 풀이는 아래와 같다.

import java.util.*;

public class Main {

	private static int max = 0;
	private static int min = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int N = in.nextInt();
		findAll(N, calcOdds(N));
		System.out.println(min + " " + max);
	}

	private static void findAll(int num, int odd) {
		if (num < 10) {
			max = Math.max(max, odd);
			min = Math.min(min, odd);
			return;
		}

		if (num < 100) {
			int newNum = num / 10 + num % 10;
			int newOdd = calcOdds(newNum);
			findAll(newNum, odd + newOdd);
			return;
		}

		int length = (int) Math.floor(Math.log10(num)) + 1;
		for (int firstLength = 1; firstLength <= length - 2; firstLength++) {
			for (int secondLength = 1; secondLength <= length - firstLength - 1; secondLength++) {
				int thirdLength = length - firstLength - secondLength;

				int secondPow = (int) Math.pow(10, secondLength);
				int thirdPow = (int) Math.pow(10, thirdLength);

				int firstNum = num / secondPow / thirdPow;
				int secondNum = (num / thirdPow) % secondPow;
				int thirdNum = num % thirdPow;

				int newNum = firstNum + secondNum + thirdNum;
				int newOdd = calcOdds(newNum);
				findAll(newNum, odd + newOdd);
			}
		}
	}

	private static int calcOdds(int num) {
		int sum = 0;
		while (num != 0) {
			sum += (num % 10) % 2;
			num /= 10;
		}
		return sum;
	}
}

문제 조건

• 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다.
• 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. (짝수번째는 숫자, 홀수번째는 연산 기호)
• 연산자는 +, -, * 중 하나이다.
• 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다. 단, 괄호는 중첩되면 안된다.

수식의 길이 1 ≤ N ≤ 19이므로 dfs를 이용하여 완전 탐색을 해도 시간 초과가 나지 않을 것이다.

괄호를 묶는 방법은 (a+b)+c, a+(b+c) 두 가지 방법으로 나누어 계산한다.

import java.util.*;

public class Main {
	public static long max = Integer.MIN_VALUE;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String s = in.next();
		char[] expression = s.toCharArray();

		if (n == 1) {
			System.out.println(s);
		} else {
			dfs(expression[0] - '0', 1, expression);
			System.out.println(max);
		}
	}

	public static void dfs(long result, int index, char[] expression) {
		if (index + 1 >= expression.length) {
			max = Math.max(max, result);
			return;
		}

		// (a+b)+...
		long resultFront = calculate(result, expression[index], expression[index + 1]);
		dfs(resultFront, index + 2, expression);

		// a+(b+c)+...
		if (index + 3 < expression.length) {
			long resultBack = calculate(expression[index + 1], expression[index + 2], expression[index + 3]);
			dfs(calculate(result, expression[index], resultBack), index + 4, expression);
		}

	}

	public static long calculate(long a, char op, long b) {
		switch (op) {
		case '*':
			return a * b;
		case '+':
			return a + b;
		case '-':
			return a - b;
		}
		return 0L;
	}

	public static long calculate(long a, char op, char b) {
		return calculate(a, op, (long) (b - '0'));
	}

	public static long calculate(char a, char op, char b) {
		return calculate((long) (a - '0'), op, (long) (b - '0'));
	}
}

문제 조건

레스토랑의 구조는 완전히 동그란 모양이고, 외벽의 총 둘레는 n(미터)이며, 외벽의 몇몇 지점은 취약한 지점들이 있다.

따라서 내부 공사 도중에 주기적으로 점검을 한다. 점검 시간을 1시간으로 제한된다.

친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하려고 한다.

편의상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타낸다.

친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동한다.

예제는 아래와 같고, 어디서든 출발하면서 특정 시간동안 많은 취약점을 찾도록 하면 되는 것 같다.

n = 12
weak = [1, 5, 6, 10]
dist = [1, 2, 3, 4]
=> answer = 2

일단 1 <= n <= 200, weak의 길이는 1 이상 15 이하, dist의 길이는 1 이상 8 이하이다.

수의 범위가 굉장히 작아서 완전탐색을 해도 될 것 같다고 생각했다.

문제 풀이 과정은 아래와 같다.

1. 일단 모든 경우의 수(순열)을 뽑는다.

2. 순열이 외벽 점검을 만족하는지 확인하고 인원수를 업데이트 해 준다.

• weak = [1, 5, 6, 10]이라면 [1, 5, 6, 10], [5, 6, 10, 13], [6, 10, 13, 17], [10, 13, 17, 18]의 외벽점검을 시작한다.
• 적은 수의 순열부터 구한 다음에 min 값이 업데이트 되면 그 뒤는 계산하지 않도록 한다.

import java.util.*;
class Solution {
	public static int min = Integer.MAX_VALUE;

	public int solution(int n, int[] weak, int[] dist) {
		boolean[] isVisited = new boolean[dist.length];
		int[] output = new int[dist.length];

		for (int i = 1; i <= n; i++) {
			permutation(dist, output, isVisited, 0, n, i, weak);
			if (min != Integer.MAX_VALUE) {
				break;
			}
		}

		if (min == Integer.MAX_VALUE) {
			min = -1;
		}
		return min;
	}

	public static void permutation(int[] dist, int[] output, boolean[] visited, int depth, int n, int r, int[] weak) {
		int length = dist.length;

		if (min < r) {
			return;
		}

		if (depth == r) {
			if (isPossible(output, n, r, weak)) {
				min = Math.min(min, r);
			}
			return;
		}

		for (int i = 0; i < length; i++) {
			if (visited[i] != true) {
				visited[i] = true;
				output[depth] = dist[i];
				permutation(dist, output, visited, depth + 1, n, r, weak);
				visited[i] = false;
			}
		}
	}

	public static boolean isPossible(int[] output, int n, int r, int[] weak) {
		if (min <= r) {
			return true;
		}

		int length = weak.length;
		for (int start = 0; start < length; start++) {
			int userIndex = 0;
			int before = weak[start];
			boolean possibleUnit = true;

			for (int i = start; i < start + length; i++) {

				int now = weak[i % length];
				if (i >= length) {
					now += n;
				}
				if (now - before > output[userIndex]) {
					userIndex++;
					before = now;
				}

				if (userIndex >= r) {
					possibleUnit = false;
					break;
				}
			}
			if (possibleUnit) {
				return true;
			}
		}
		return false;
	}
}

쉬운 완전 탐색 문제

import java.util.Scanner;

public class Solution {
	public static int max = 0;

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		int testcase = in.nextInt();
		for (int t = 1; t <= testcase; t++) {
			max = 0;
			int n = in.nextInt();
			int limitCalories = in.nextInt();
			int ingredients[][] = new int[n][2];

			for (int i = 0; i < n; i++) {
				ingredients[i][0] = in.nextInt();// 맛
				ingredients[i][1] = in.nextInt();// 칼로리
			}

			for (int i = 0; i < n; i++) {
				findMaxTaste(i, ingredients[i][0], ingredients[i][1], ingredients, limitCalories);
			}

			System.out.println("#" + t + " " + max);
		}
	}

	public static void findMaxTaste(int index, int taste, int calories, int ingredients[][], int limit) {
		if (calories > limit || index == ingredients.length) {
			return;
		}

		max = Math.max(max, taste);

		for (int i = index + 1; i < ingredients.length; i++) {
			if (calories + ingredients[i][1] <= limit) {
				findMaxTaste(i, taste + ingredients[i][0], calories + ingredients[i][1], ingredients, limit);
			}
		}
	}
}