[백준/baekjoon] 2798번 블랙잭 (파이썬, c++)

내 제출

- 바로 아래 코드는 python

- c++ 코드는 이 글 제일 아래에 더보기를 누르면있다.

# 첫째 줄에 카드의 개수 n,m이 주어진다.
n, m = map(int, input().split())

# 둘째 줄에 카드에 쓰여 있는 수가 주어진다.
# 입력 받은 카드들을 index 붙여서 순서대로 놓고 뽑기 위해 list 에 담음.
card_list = list(map(int, input().split()))

# 합들의 모음
card_sum = set()

# 카드 리스트에서 순서대로 앞에서부터 카드 세 장 뽑을 예정
for i in range(len(card_list)-2):
    # 앞에서 card_list[i]번째까지 선택했으니까 다음 선택은 i+1번째 부터 가능.
    for j in range(i+1, len(card_list)-1):
        # 앞에서 j번째 까지 선택했으니까 j+1번째 카드부터 선택
        for k in range(j+1, len(card_list)):
            # 고른 세 카드의 합
            tmp_sum = card_list[i] + card_list[j] + card_list[k]
            # 합이 m 이하인 것들만 취급
            if tmp_sum <= m:
                card_sum.add(tmp_sum)

# 카드 3장의 합이 M 이하이면서 가장 가까운 것을 출력.
# 모아둔 합들의 모음 중 가장 큰 값이면 됨.
print(max(card_sum))

 

문제 접근(풀이)

- 수학적으로 생각했을 때 무작위로 3개 뽑는다...

- 카드  n개 * (n-1) * (n-2) 나누기 6.. 복잡도가 어쨌든 O(n^3)

- 3중첩 반복문...? (근데 이게 맞나...? 일단 써 봄)

# 0 번 카드부터 뽑아서 합을 구한다고 할 때 카드 뽑는 순서 생각해보면
# 0 번 카드 - 1번 카드 - 2번 카드
# 0 번 카드 - 1번 카드 - 3번 카드
# 0 번 카드 - 1번 카드 - ..마지막 카드
# 0 번 카드 - 2번 카드 - 3번 카드
# 0 번 카드 - 2번 카드 - 4번 카드
# 0 번 카드 - 2번 카드 - ..마지막 카드
# ... 0번 카드를 처음 뽑았을 때 의 경우의 수가 다 하면 1번 카드 뽑음
# 1번 카드 - 2번 카드 - 3번 카드... 마지막 카드
# 1번 카드 - 3번 카드 - 4번 카드 ... 마지막 카드

 

- 경우의 수는 이렇게...

- 첫 번째 반복문 범위는 0번째 카드부터~ 마지막에서 세 번째 카드까지 (뒤에 두 개 뽑아야 하니까 2개는 남겨둬야 함.)

- 두 번째 반복문 범위는 앞에서 뽑은 카드 바로 다음 것부터~ 마지막에서 두 번째 카드까지 (뒤에 뽑을 한 개 남겨둠)

- 마지막 카드는 앞에서 뽑은 카드 다음부터 마지막 카드까지 아무거나 뽑아도 됨.

- 어떤 카드들의 합인지 구하는 게 아니라 합만 구하면 되니까 겹치는 합 제거하기 위해서 집합(set) 을 사용.

 

채점 결과

 

▽C++ 풀이

c++ 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N, M, goal=0, sum = 0;
	vector<int> card;

	cin >> N >> M;

	card.clear();
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		card.push_back(tmp);
	}

	for (int i = 0; i < N - 2; i++)
		for (int j = i + 1; j < N - 1; j++)
			for (int k = j + 1; k < N; k++)
			{
				sum = card[i] + card[j] + card[k];
				if (sum <= M && sum > goal) {
					goal = sum;
				}
			}

	cout << goal;
}

 

채점 결과

 

사담

어려운 건 없었는데 회사 다닐 때도 3중첩은 한 번 밖에 못 봤었어서 작성하면서 이게 맞나... 했다.

이전에 c++ 로 제출해 둔 게 있길래 그 코드 오랜만에 봤는데 어쨌든 이 주제(단계별로 풀기 - 브루스 포스)는 이렇게 푸는 게 맞나보다.

 

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

2798번: 블랙잭