백준 C++ 2798번 블랙잭 ( 브루트포스 )

출처 : 제5인격 나무위키

 

안녕하시오!

 

제가 가끔 하는 게임

제5인격에 있는 미니게임 블랙잭이 생각나서 가져와봤습니다.

 

오늘은

카드게임

블랙잭을

해보.. 진 않고

코드를 짜보겠습니다.

---

 

 

 

블랙잭 변형게임으로

5장이 있을 때 3장을 골라서, 21에 가장 가까운 수를 만드는 것

 

N의 범위가 3부터 100이니까..

그냥 다 곱해주면 안 되려나...

100*99*98 이니까..

1000000 이면 돌아가지 않을까..

 

그럼.. for문을 3개....

 

해보자!

 

ㅋㅋㅋㅋㅋ

긁적.. 굉장히 수고스러운 문제..

m과 같으면 출력 후 탈출

m보다 작으면

기존값과 비교 후 큰 수 넣어두기.. 그리고 출력

 

진짜 이 하찮은..(?) 식이

 

 

네..?!

 

인지 씨에게 달려갔다.

 

인지 씨.. 최고의 답은 무엇인가요.

 

헉..

 

그리고 몇 가지 조언을 해주었다.

 

1. 벡터는 최대한 0부터 시작하세요.

이상한 값에 접근할 수도 있습니다.

 

위에서 0부터 v [i]를 해주었기 때문에

v [n]는 쓰레기값이 들어있을 것이다.

그래서 이렇게 for문에 n이 아니라

i < n - 2를 해주는 것이 좋다고 한다

j < n - 1

k < n

이렇게 해주면 인덱스 초과가 안 난다고 한다.

 

더 쉽게 말하면

A B C D E가 있는데

i를 D나 E로 해버리면

j와 k는 고를게 없어진다

즉 , 최소한 두 개를 남겨둬야 하기 때문에

n-2까지 해줘야 한다는 뜻이다!!!

 

---

 

이문제는 100개가 한 정이었기 때문에 이렇게 푸르트푸스로 풀 수 있었다.

하지만 만약에 2800개씩 커진다면 어떻게 될까?

시간초과가 분명 날것이다.

 

그럴 때 O(N^2)인 고급기법은 투 포인터 라고 한다

 

투포인터는

1. 오름차순으로 정리한다.

2. 첫 번째 카드 ( i )를 고정한다.

3. 양 끝단에 포인터 두 개를 둔다 ( right, left )

4. 세 카드의 합이

M보다 크면 숫자를 줄여아하니 right를 왼쪽으로 옮기고

M보다 작으면 숫자를 키워야 하니 left를 오른쪽으로 옮긴다.

 

그래서 시작은?

 

sort(v.begin(), v.end());

int i = 0;

int left = i+1;

int right = n-1;

 

로 해주고

while(left < right)로 루프를 돌게 한다.

 

left가 right보다 커지면 순서가 이상해지고

left와 right가 만나면 더 이상 조합할 숫자가 없어지기 때문!

 

int sum = v [i] + v [left] + v [right];

로 미리 오타 나지 않게 변수 만들어주고

 

위에 풀었던 거처럼 

sum == m 이면 그냥 출력, return 0;

그리고 if문을 또 만들어서 sum < m 이면

m보다 작은 거니까 일단 ans = max(ans, sum); 해주고

left ++;  로 숫자를 키워봅니다.

 

else sum > m 이면

이러면 답에도 들어가면 안 되니까 right--; 해줍니다.

 

 

자잔..!!

투포인터도 조금(?) 학습 완

---

 

아 그리고 벡터 넣는 것 좀!!! 기억하자

또 까먹어서 찾아봤다.

 

그래 고생했다.

잘했다.

 

 

가끔은 그렇게 완전탐색이 도움이 되는구나.

나도 이제 시간복잡도를 조금 생각하는 사람이 되었구나 싶어

아주 조금 뿌듯했다.