(백준, 파이썬)블랙잭블랙블랙잭잭블랙 (06-28 해결)

롤 그때 그 시절 사기템

(2022-06-14)

최근 CS50을 수강하면서, 시간복잡도와 의사코드에 대해 알게 되었다.

시간복잡도는 아직 익숙하지 않고, 더 배워야할 것 같지만,

의사코드는 이전에 내가 문제를 풀면서 주석을 달듯이 먼저 설계해보는 그런 과정인 것 같다.

이 스타일이 맘에 들어서 앞으로 문제를 풀 때는 의사코드를 작성해보고 구현하는 연습을 해보려고 한다.

+ 시간복잡도도 구해보고!

---

2주가 지난 지금 드디어 풀었다.

---

-오늘 풀 문제-

재귀가 아니라 브루트포스를 풀 것이다

 

브루트포스 알고리즘(Brute Force) : '야만적으로', '꼼꼼히', '모든 경우'를 찾는다.

---

2798 - 블랙잭

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

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다.

카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다.

블랙잭은 카지노마다 다양한 규정이 있다.

 

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다.

그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다.

그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다.

블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

 

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

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

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

---

---

1. 첫째줄에 카드의 개수(N)과 목표치인 합(M)을 입력받는다.

2. 둘째줄에 N개의 카드에 쓰여 있는 숫자를 공백을 사이에 두고 정렬되지 않은 상태로 입력 받는다.

3. 2번의 값들을 리스트로 정렬해서 받는다.

4. 정답 후보 리스트를 선언한다.

5. 3의 리스트의 끝 값에 그 이전 값을 더해서 M을 넘지 않으면 맨 첫 번째 값을 더하고, 그 값이 M을 넘지 않으면 다음 값을 .... 진행한다.

6. 위 과정에서 M을 넘기는 순간, 그 이전의 값을 4에 append하고... 하는 식으로 진행한다.

6. 후보리스트에서 가장 높은 값을 출력한다.

 

---

그렇게 해서, 구현하려고 하는데..

잘 안 된다.

일단 내일 들어와서 풀고, 수정해야겠다.

---

- 맞힌 코드 -

(2022-06-28)

#달라진 점

1. 못 풀다가 풀었음

2. 굴러가는 횟수 판단해서 브루트포스로 풀 수 있는 걸 체크했음

3. 구현 했음

 

리스트를 거꾸로 안 돌려도 상관이 없는 풀이가 되긴 했지만,

3중 for문으로 카드끼리는 중복이 없으니 같으면 건너뛰게 해줬고,

각 카드의 값이 target 값보다 작고 + 기존의 최고값보다 높으면 갱신하게 설정했다.

 

2주전의 나보다 진화했을지도?

성공!

---