Baekjoon - 2798

문제

Solved.ac Class2+

1차시도

결국 모든 경우의 수를 찾아서, 그중 가장 큰 수를 찾아야 한다

public class Main {
	private static Stack<Integer> selectCards = new Stack<>();

	private static int maxValue = Integer.MIN_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int m = Integer.parseInt(split[1]);
		String[] stringCards = br.readLine().split(" ");
		ArrayList<Integer> cards = new ArrayList<>();

		for (String card : stringCards) {
			cards.add(Integer.parseInt(card));
		}

		findOut(0, m, n, 0, cards);

		System.out.println(maxValue);

	}

	private static void findOut(int deep, int m, int n, int start, ArrayList<Integer> cards) {
		if (deep == 3) {
			int sum = 0;
			for (Integer selectCard : selectCards) {
				sum += selectCard;
			}
			if (sum <= m && maxValue < sum) {
				maxValue = sum;
			}
			selectCards.pop();
			return;
		}

		for (int i = start; i < n; i++) {
			selectCards.add(cards.get(i));
			findOut(deep + 1, m, n, i+1, cards);
		}
		if (deep == 0) {
			return;
		}
		selectCards.pop();

	}
}

deep을 경우의 수로 주고 3에 도달하면 합을 확인하고 조건에 부합하면 maxValue값을 바꿔준다.

for (int i = start; i < n; i++) {
			selectCards.add(cards.get(i));
			findOut(deep + 1, m, n, i+1, cards);
		}

이 부분에서 카드를 넣어주었다

if (deep == 0) {
			return;
		}
		selectCards.pop();

이부분에서 카드를 빼주었는데 생각해 보니까 굳이 그럴필요없이 넣고 바로 빼버리면 될것같다.(멍청이)

그래서 글을 작성하면서 저부분을 바꾸었다

개선판

public class Main {
	private static Stack<Integer> selectCards = new Stack<>();

	private static int maxValue = Integer.MIN_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int m = Integer.parseInt(split[1]);
		String[] stringCards = br.readLine().split(" ");
		ArrayList<Integer> cards = new ArrayList<>();

		for (String card : stringCards) {
			cards.add(Integer.parseInt(card));
		}

		findOut(0, m, n, 0, cards);

		System.out.println(maxValue);

	}

	private static void findOut(int deep, int m, int n, int start, ArrayList<Integer> cards) {
		if (deep == 3) {
			int sum = 0;
			for (Integer selectCard : selectCards) {
				sum += selectCard;
			}
			if (sum <= m && maxValue < sum) {
				maxValue = sum;
			}
			return;
		}

		for (int i = start; i < n; i++) {
			selectCards.add(cards.get(i));
			findOut(deep + 1, m, n, i+1, cards);
			selectCards.pop();
		}

	}
}

조금 더 깔끔하다.

해결