쉬운 프로그래밍

[알고리즘] 백준 2798 블랙잭 - JAVA 본문

알고리즘/Brute Force

[알고리즘] 백준 2798 블랙잭 - JAVA

쉬운형 2021. 3. 24. 14:11

www.acmicpc.net/problem/2798

 

2798번: 블랙잭

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장

www.acmicpc.net

쉬운거라,,, 풀이는 따로 생략해도 될 것 같다.

 

 

백트래킹 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

    static int n;
    static int m;
    static int[] card;
    static int max = 0;

    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        card = new int[n];
        visited = new boolean[n];

        s = br.readLine();
        st = new StringTokenizer(s, " ");

        for (int i = 0; i < n; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }

        bruteForce(0, 0);
        System.out.println(max);
    }

    static void bruteForce(int depth, int sum) {

        if (depth == 3) {
            if (sum <= m) {
                max = Math.max(max, sum);
            }
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                bruteForce(depth + 1, sum + card[i]);
                visited[i] = false;
            }
        }
    }
}

 

브루트포스 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

    static int n;
    static int m;
    static int[] card;
    static int max = 0;

    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        card = new int[n];
        visited = new boolean[n];

        s = br.readLine();
        st = new StringTokenizer(s, " ");

        for (int i = 0; i < n; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    int sum = card[i] + card[j] + card[k];

                    if (sum <= m) {
                        max = Math.max(max, sum);
                    }
                }
            }
        }

        System.out.println(max);
    }

}

'알고리즘 > Brute Force' 카테고리의 다른 글

[알고리즘] 프로그래머스 - 카펫 - JAVA  (1) 2021.08.18
[알고리즘] 프로그래머스 - 모의고사 - JAVA  (0) 2021.08.14
[알고리즘] 백준 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - JAVA  (0) 2021.04.15
[알고리즘] 백준 2503 숫자야구 - JAVA  (0) 2021.03.25
'알고리즘/Brute Force' Related Articles more
Comments