블랙잭 - 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장의 합을 출력한다.

풀이

하.. 재귀라는 것을 현재 약 나흘정도 들여다본 결과, 이제 약간 응용이 가능해지고 있는 것 같다. 물론 어느정도 패턴 암기를 통하는 현상이긴 하다만 이 정도도 유의미한 성과인지라 다행이다.

모든 조합의 경우의 수를 확인하는 문제를 brute force라고 한다고 한다. 이 경우 두 가지 풀이가 있는데 아래가 처음의 풀이이다. 매우 쉽다.

itertools - combinations을 이용한 답안

import sys
from itertools import combinations
input = sys.stdin.readline

N, M = map(int, input().split())
cards = list(map(int, input().split()))

totalSum = -1e9

for c in combinations(cards, N):
	tempSum = sum(c)
	if tempSum>totalSum and tempSum<=M:
		totalSum=tempSum

print(totalSum)

반복문 c는 "cards 중 N개를 뽑은 모든 조합 하나하나"이다. (c의 자료형은 기본적으로 튜플.)
알고리즘 연습을 계속하다보니 컨벤션과 같은 개념으로 사람들이 많이들 사용하는 요령들을 알게 되었다. 여러 경우 중 최댓값을 도출해낼 때 일단 변수로 개 작은 숫자 "-1e99"같은 걸 선언한 뒤 여기에 차곡차곡 더 큰 경우의 수를 재할당해서 최댓값을 구하는 거다. 이게 위 코드 중 totalSum의 의의이다.

어쨌든 이런 식으로 쉽게 구하는데, 이를 이제 combination이 아닌 직접 모든 조합을 찾는 코드로 구현하였다.

재귀법을 이용한 답안

import sys
input = sys.stdin.readline

currMax = -1e9
ontable = list()

def recur(c, start):
    global currMax
    
    if c==3:
        if sum(ontable)>currMax and sum(ontable)<=M:
            currMax = sum(ontable)
        return
        
    for start in range(start, N):
        ontable.append(int(cards[start]))
        recur(c+1, start+1)
        ontable.pop()

N, M = map(int, input().split())
cards = list(map(int, input().split()))

recur(0, 0)
print(currMax)

우리는 위 combination을 이용했던 때와 동일한 방식으로 문제를 풀 것이다. 같은 의의로 변수 currMax가 선언됐다. 변수 ontable은 말 그대로 "현재 테이블 위에 올려져 있는 카드의 조합 경우"를 담는 임시보관함 변수이다.

재귀를 입문하고 약 백 몇 시간이 되었는 지금 나름의 눈썰미 아닌 눈썰미가 붙었는데, 이는 다음과 같다.

1. 재귀를 구현하는 과정을 역순으로 생각해본다. 재귀법을 사용하기 위해선 가장 먼저, 재귀를 탈출 조건을 떠올려 보자.

이 조건을 가장 먼저 써본다. 이 조건문에 언제 답이 딱 맞아 return 되는지? 또한, 우리의 함수는 최종 return 전까지 이 조건문에 계속 튕겨서 recur(n-1) 또는 recur(n+1)가 호출되었던 그 구간으로 돌아가야 할 것이다. 그 점을 잘 기억해 먼저 적는다.
--> 이것을 어려운 말로 하면 'base case'이라고 한다. base case 구간을 함수 정의 가장 상단에 써 놓는 것이 좋은 것 같다.

2. 사람들이 재귀함수를 이용해 알고리즘 문제를 풀이하는 간단한 패턴들이 있다.

인덴테이션에 주의. 열심히 적었는데 미리보기에서 인덴테이션 다 없어져서 걍 캡쳐함.
+ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
ㅣ def recurExample(인자A, 인자B, 인자C, ..):
ㅣ if 재귀뎁스가 숫자 N에 다다르면,
ㅣ if 탈출 조건에 해당하게 되었다면,
ㅣ print라던가 변수 재할당이라던가 최종 답에 대한 할 일
ㅣ return
ㅣ
ㅣ for i in range(아마도 인자, 인자, ..):
ㅣ 주로 리스트변수 등장하고 여기에 대한 반복수행 전에 해야하는 일정의 쎗팅
ㅣ recurExample(인자A+1, 인자B+1, ..)
ㅣ 리스트변수.pop() 혹은 recurExample 한 바퀴 돌고 옮에 의해 변형된 무언가를 복원하는 일
ㅣ
ㅣ recurExample(반복의 맨 처음 쎗팅)
ㅣ
어쨌든,
이것이 가장 이해하기도 외우기도 쉬운 기본의 재귀 틀인 것 같다. 내가 기억하려고 걍 적었으니 못 알아보겠는 누군가가 있다면 화이팅.. 위 요약은 거의 가장 쉬운 문제들을 풀 때의 예시에 가까운 정도이고 더 어려운 문제들 가면 당연히 더 복잡해진다.

아까 가장 먼저 떠올링 탈출 조건은 상단, 그 아래는 그냥 반복문 적듯이 자연스레 for부터 적어본다. ---> 이 영역은 recursive case이다.

recurExample(인자A+1, 인자B+1, ..) <-- 여기 부분에서 인자의 값을 순차적으로 변경할 것인데, 이는 결국 아까 적은 탈출조건에 한 발짝 한 발짝 가까워지는 실행조건이 된다. 이 부분은 실제 문제마다 n+1, n//2 등등 다양하다... 당연한 얘기.
동시에, 한 함수 안에 재귀가 두 구간 이상에서 일어나면 해당 재귀 구간이 언제 어떻게 return 되는 지에 대한 정보가 된다.

3. 재귀를 사용하면 뭔가 식이 비어보인다. 꼭 선언되야 할 것 같은 변수가 안 선언되고 진행된다. 반복문이 붙어야 할 것 같은 지점에서 반복문이 재귀식으로 대체된다.

그래서 당황스러울 수 있으나 현재 순환하고 있는 조건과 횟차 같은 걸 생각해보면 된다.

4. 함수를 짤 때, 내가 지금 반복문의 실행 중간에 있다고 생각해보자.

재귀는 계속해서 같은 함수를 호출하는 기법이다. 하나의 수행이 재귀될 예정에 있다면 그 이전과 다음 그 사이에 현재 내가 계획하는 수행을 설계한다고 생각하도록 해본다.

5. 코드는 컴퓨터와 사람이 소통하는 언어이다. 사람이 쓰고 사람이 읽는 글과 닮았지만 또 좀 달라서, 위에서부터 아래로 순서대로 읽는 것이 아니라 실행되는 지점에서부터 읽어야 한다.

그래서 이것을 깨닫는다면 코드가 실행되는 순서대로 읽게 되며, 그 습관이 생기면 알고리즘이 훨씬 reachable하게 되는 것 같다. 문제를 잘 읽고, 풀이에 따라 함수의 예상 진행을 먼저 떠올려보자...

그래서
블랙잭으로 돌아오면
사실은 매우매우 쉬운 문제임을 알 수 있다....

사람이 아닌 컴퓨터의 입장에서 생각해보자.

수도코드
N개의 카드 중 하나를 뽑는다.
-> 어떤 보관함 1에 그걸 보관한 다음, 하나 더 뽑는다. 하나 더 뽑는다. 3장이 됐으니 뽑는 행위를 멈춘다.
-> 보관함 안의 것들을 도합한 것이 M보다 작되 아까의 경우 도합보다 더 커? 아까와 지금 것 둘 중 더 큰 게 뭔지 확인 후, 하나만 보관. 이건 보관함 2이다. (위의 4. 항목을 봐보면.... 마치 현재 내가 반복문의 첫번째 실행이 아닌 n번째 실행 중에 있다는 가정 하에 함수를 적어보는 것이다.)
-> 확인했으면 이제 아까의 보관함 1에서 방금 넣은 숫자 하나만 뺀다. 같은 수행을 또 시작.

아래는 위의 수도코드를 코드로 표현해본 것이다.

    for start in range(start, N):
        ontable.append(int(cards[start]))
        recur(c+1, start+1)
        ontable.pop()

철저하게 잘 적진 않았지만 어쨌든 이런 식으로 접근하다 보면 뭔 소린지 알 수 있게 된다.