백준알고리즘:p2798 블랙잭

분류: 브루트 포스

 

▶문제

(예제입력1) 5장을 뽑으라고 한 후, "3장의 카드 합으로 21과 가장 가깝게 만들어라", 그 다음에 자신의 카드 5장을 확인하는 플레이어

▶코드

//백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 
//package이름도 뺴야함
package bruteForce;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p2798 {

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try{ 
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int size = Integer.parseInt(st.nextToken());
			int[] cards = new int[size];
			int number = Integer.parseInt(st.nextToken());
			StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
			for(int i=0; i<size; i++) {
				cards[i] = Integer.parseInt(st2.nextToken());
		}
		br.close();
		//다른 세 수를 더한 거에 number를 넘지 않으면서 가장 큰 수 구해라..
		int compare = number;
		int result = 0;
		for(int i=0; i<size-2; i++) {//숫자A-마지막 두 수 남겨놔야 해서 2작게 돌아야됨
			for(int j=i+1; j<size-1; j++) {//숫자B
				for(int k=j+1; k<size; k++) {//숫자C
					int temp = number-(cards[i]+cards[j]+cards[k]);
					if(temp<=compare&&temp>=0) {
						compare = temp;
						result = number-compare;
					}
				}
			}
		}
		System.out.print(result);
		}catch(Exception e) { e.printStackTrace(); }
		}
	}

3월1일까지 연휴로 쉬었다 생각하고 다시 열심히 하자!

 

▶브루트 포스(brute force) 알고리즘

문제를 해결하기 위해서
가능한 모든 경우에 대해 모두 직접 해 보는 방법이라고 한다.

그래서 경우의 수만큼의 시간 복잡도를 가진다. 

그만큼 정확도도 100%인 것!

 

▶서로 다른 세 수의 합이니까, 각 배열 인덱스가 달라야 함.

i는 0부터 size-2

j는 i+1부터 size-1

k는 j+1부터 size끝까지

 

▶차이 compare = 말한 숫자-세수를 더한 값

세 수를 더한 걸 괄호로 묶어줘야 하는데 빼먹는 이상한 실수를 했다...

또, result는 세 수의 합인건데 compare+number를 하는 이상한 식을 세웠다..

그러니 계속 틀렸지

말한 숫자-compare을 해줘야 한다.

 

▶DataInputStream을 써서 readInt를 해보려고 했는데, 이상한 숫자가 읽혔다.

따로 해보기

---

채점결과

result를 compare과 number를 합한 결과로 해서 계속 틀렸다..

 

링크 www.acmicpc.net/problem/2798

2798번: 블랙잭