lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read




문제 풀이

이 문제는 브루트포스, 즉 완전탐색 알고리즘을 활용하여 푸는 대표적인 문제라고 한다.
완전탐색 알고리즘은 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다.


아이디어 도출

N개의 카드중에서 3장을 택하여 M과 같거나 가장 가까운 수를 만들어야 한다.
M과 같거나 근접한 수를 만들기 위해 생각한 아이디어는 다음과 같다.

  • N개의 카드들 중에서 순서대로 3장을 뽑는다. 이때, 1장을 뽑았으면, 뽑은 1장은 제외하고 N-1개중에서 새로운 1장을 뽑는다.
  • 뽑은 3장의 합이 M과 같을 때까지 max에 저장해나간다.
  • 뽑은 3장의 합이 M과 같다면 3장의 합을 출력하고 더 이상 카드를 뽑지 않아도 되니 반복문을 탈출한다.


이제 코드를 작성해보자.

1
2
3
4
5
6
7

Scanner sc = new Scanner(System.in);
StringTokenizer st = new StringTokenizer(sc.nextLine());

int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String[] cards = sc.nextLine().split(" ");
int max = 0;

Scanner를 통해 카드개수 N과 블랙잭 수 M, N개의 카드뭉치들을 입력받는다.
그리고 3장의 카드를 뽑아가며 합을 저장해둘 max 변수를 초기화한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 3중 반복문을 통해 3장의 카드을 순서대로 뽑는다.
for(int i=0; i<cards.length; i++) {
    for(int j=i+1; j<cards.length; j++) {
        for(int k=j+1; k<cards.length; k++) {
            int sum = Integer.parseInt(cards[i])+Integer.parseInt(cards[j])+Integer.parseInt(cards[k]);
            if(sum < M) max = Math.max(max, sum);
            else if(sum == M) {
                max = sum;
                System.out.println(max);
                return;
            }
        }
    }
}
System.out.println(max);

3중 for문을 통해 뽑은 카드를 제외한 다음 카드를 뽑아가는 방식으로 중복되지 않는 3장의 카드들을 뽑아 sum(합)을 구한다.
그리고 sum이 M과 같아질 때까지 max에 sum을 저장해나간다. 만약 3장을 모두 뽑았는데도 합이 M보다 작다면 M과 가장 근접한 수를 출력해야 하기 때문이다.

또한 sum이 M과 같다면 max에 sum을 저장하고, max를 출력하고 return하여 삼중 for문을 종료시킨다.

  • 이 때, break문을 사용하지 않는 이유는 별도의 예외 처리 없이 바로 3개의 반복문을 종료하기 위해서이다.
  • sout를 통해 출력을 한 이유는 반복문에서 return을 활용해 함수를 종료하기에 BufferedWritter가 아닌 sout를 활용하였다.
    • BufferedWritter에 담아두었다가 출력하는 방식인데 그 전에 return을 하기 때문에 출력이 되지 않는다.



작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(sc.nextLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        String[] cards = sc.nextLine().split(" ");
        int max = 0;
        
        for(int i=0; i<cards.length; i++) {
            for(int j=i+1; j<cards.length; j++) {
                for(int k=j+1; k<cards.length; k++) {
                    int sum = Integer.parseInt(cards[i])+Integer.parseInt(cards[j])+Integer.parseInt(cards[k]);
                    if(sum < M) max = Math.max(max, sum);
                    else if(sum == M) {
                        max = sum;
                        System.out.println(max);
                        return;
                    }
                }
            }
        }

        System.out.println(max);
    }   
}

회고

  • 카드 3장을 뽑아가면서 연산을 진행하였는데, 3중 for문에서의 탈출을 return이 아닌 다른 예외처리 방식으로도 접근해봐야겠다.
  • BufferedWritter의 경우 버퍼에 출력물을 모두 담아두었다가 출력하는데, 반복문 내에서의 return문 때문에 사용하지 못하였다. BufferdWritter의 출력시점과 return문 시점에 대해서 적절한 상황에 사용할 수 있도록 꼭 찾아보고 공부해야겠다.

You may also enjoy