반응형
문제
https://www.acmicpc.net/problem/2798
2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
풀이
이 문제는 완전탐색으로 풀이할 수 있습니다.
3장의 카드를 뽑는 모든 경우의 수를 확인하고, M에 최대한 가까운 카드의 합을 확인하기 위해서는
3중 중첩 for문을 사용해서 풀이할 수 있습니다.
시간복잡도는 $O(n^3)$이 될 것이고, n이 최대 100이므로 $100^3 = 1,000,000$의 연산이 소요될 것 입니다.
1초에 약 1억번 연산이 가능하다고 가정하면, 충분합니다.
소스코드
후기
3장의 카드를 뽑는 모든 경우의 수를 확인하여서 풀 수 있는 문제입니다.
combination을 구현해도 무방하지만, 3장을 뽑는것으로 고정되어있기 때문에 3중 중첩 for문으로 쉽게 풀이할 수 있습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 7568 덩치 (Swift) (1) | 2023.03.13 |
|---|---|
| [BOJ] 백준 2231 분해합 (Swift) (0) | 2023.03.13 |
| [BOJ] 백준 18870 좌표 압축 (Swift) (0) | 2023.03.10 |
| [BOJ] 백준 10814 나이순 정렬 (Swift) (0) | 2023.03.10 |
| [BOJ] 백준 1181 단어 정렬 (Swift) (0) | 2023.03.08 |
