[Algorithm] 백준/Bronze/2798. 블랙잭

하루입니다.

 

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

2798번: 블랙잭

 

---

 

블랙잭 ^^ ...

 

백준의 단계별 문제 중 브루트포스 첫번째에 있는 문제이다.

목표 : n장의 카드가 주어질 때, m과 가장 가까운 카드 3장의 합을 구해 출력하자.

 

세 가지 방법으로 풀 것이다!

1. while + BufferedReader

2. 삼중 for문 + BufferedReader

3. 2번의 방식인데 조금이라도 시간복잡도 줄이기 

 

---

 

먼저 아래는 내가 푼 방식이다.

1. n, m을 받는다.
2. 숫자들을 배열을 사용해서 받는다.
3. 최댓값을 저장할 int max를 선언한다.
4. 커서(?) 개념 세 개를 만들었다. c1, c2, c3

4. c1 c2 c3에 위치한 값들을 모두 더하고, 만약 max보다 크다면 max에 넣는다.

5. 이 과정을 반복하다가 만약 c3가 arr.length-1와 같아지는 순간이 온다면, c2++를 하고, c3는 c2 + 1을 해준다.

6. 만약 과정을 반복하다 c2++값이 idx 7 이 된다면 한 턴이 끝난 것이므로, c1++, c2는 c1+1, c3는 c2+1을 해준다.

7. 만약 과정을 반복하다 c1이 idx 6이 된다면 전체 턴을 돈 것이므로 break; 하고 max를 출력한다.

 

... 

 

가 나의 답이다!

 

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

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

        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        int[] arr = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int c1 = 0;
        int c2 = 1;
        int c3 = 2;
        int max = -1;
        int l = arr.length;
        
        while(true) {
            int sum = arr[c1] + arr[c2] + arr[c3];
            if(sum > max && sum <= m) {
                max = sum;
            }
            
            c3++;
            
            if(c3 == l) {
                c2 += 1;
                c3 = c2 + 1;
                if(c2 == (l-1)) {
                    c1 += 1;
                    c2 = c1 + 1;
                    c3 = c2 + 1;
                }
            }

            if(c1 == (l-2)) {
                break;
            }
        }
        
        sb.append(max);
        System.out.print(sb);
    }
}

 

---

 

다음은 나으 사이버 알고리즘 선생님... ㅋㅋㅋㅋㅋㅋㅋ 이 푸신 방법이다.

• 알고리즘 자체는 나와 비슷하지만, 나는 while문을 사용했다면 선생님은 삼중 for문을 사용하셨다.
•  사실 while문을 사용한 이유는 for문을 언제까지 돌려야 할 지 몰라서였다. 그래서 c1이 length-2가 되었을 때 반복문을 탈출하게 하는 방식을 사용한 거였고. 이 분은 아예 for문의 조건을 길이-2, 길이-1, 길이로 주셨다.
•  또 생각해보니까 길이를 변수로 받을 필요 없이 카드 수를 사용하면 되는 거였다. 왜냐면 길이를 구하는 이유가 배열 요소 개수 구하려고 하는 건데, 그게 곧 카드 개수니까 ^ㅁ^ ...
•  또 생각해보니까 생각 못한 조건인데, m과 카드1+카드2+카드3이 같은 값을 가질 때도 그대로 리턴하면 된다. 그 이상의 값은 가질 수 없기 때문이다. 

 

 

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

class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 숫자 n과 m을 받는다.
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);
        
        // 배열을 만들고, 배열에 값을 넣는다.
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // search()의 반환값을 int max에 담는다.
        int max = search(arr, n, m);
        System.out.print(max);
    }
    
    // 최댓값을 반환하기 위한 메소드 static int search() 를 선언한다.
    static int search(int[] arr, int n, int m) {
        // 최댓값을 넣을 max를 정의한다.
        int max = -1;
        // 맨 처음은 n-2까지 반복한다. 시작값은 i=0이다.
        for(int i = 0; i < n-2; i++) {
            // 그 다음은 n-1까지 반복한다. 시작값은 j=i+1이다.
            for(int j = i+1; j < n-1; j++) {
                // 그 다음은 n까지 반복한다. 시작값은 k=j+1이다.
                for(int k = j+1; k < n; k++) {
                    // 임시로 합을 담을 변수 temp를 선언한다.
                    int temp = arr[i] + arr[j] + arr[k];
                    // 만약 temp = m인 경우, return한다.
                    if(temp == m) return temp;
                    // 만약 temp가 m 이하이면서 max보다 크다면 max를 갱신한다.
                    if(temp < m && temp > max) max = temp;
                }
            }
        }
        // 모든 순회를 마치면 result를 리턴한다.
        return max;
    }
}

 

 

 

 

---

 

다음은 위의 방법에서 조금이라도 계산을 줄이는 방법이다.

 

정답의 조건은 카드 세 장의 합이 m을 넘으면 안 된다는 점이다. 그렇다면 첫 번째 카드가 m을 넘을 때, 두 번째 카드 + 첫 번째 카드가 m을 넘을 때는 반복문을 수행하지 않게 하면 된다.

 

// 조건문을 통해 효율적으로 검색하는 법

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

class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 숫자 n과 m을 받는다.
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);
        
        // 배열을 만들고, 배열에 값을 넣는다.
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // search()의 반환값을 int max에 담는다.
        int max = search(arr, n, m);
        System.out.print(max);
    }
    
    // 최댓값을 반환하기 위한 메소드 static int search() 를 선언한다.
    static int search(int[] arr, int n, int m) {
        // 최댓값을 넣을 max를 정의한다.
        int max = -1;
        // 맨 처음은 n-2까지 반복한다. 시작값은 i=0이다.
        for(int i = 0; i < n-2; i++) {
            // 만약 arr[i]가 m보다 크다면 skip
            if(arr[i] > m) continue;
            // 그 다음은 n-1까지 반복한다. 시작값은 j=i+1이다.
            for(int j = i+1; j < n-1; j++) {
                // 만약 arr[i] + arr[j]가 m보다 크다면 skip
                if(arr[i] + arr[j] > m) continue;
                // 그 다음은 n까지 반복한다. 시작값은 k=j+1이다.
                for(int k = j+1; k < n; k++) {
                    // 임시로 합을 담을 변수 temp를 선언한다.
                    int temp = arr[i] + arr[j] + arr[k];
                    // 만약 temp = m인 경우, return한다.
                    if(temp == m) return temp;
                    // 만약 temp가 m 이하이면서 max보다 크다면 max를 갱신한다.
                    if(temp < m && temp > max) max = temp;
                }
            }
        }
        // 모든 순회를 마치면 result를 리턴한다.
        return max;
    }
}

 

---

 

 

지금은 거의 차이가 안 나지만, 입력값이 많아지면 차이도 커지지 않을까!

 

---

 

오늘도 감사합니다!

https://st-lab.tistory.com/97

 

주석 없는 코드는 여기

https://github.com/mjkim856/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Bronze/2798.%E2%80%85%EB%B8%94%EB%9E%99%EC%9E%AD