선택 트랙 알고리즘 (8일차)

<문제1>

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 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장의 합을 출력한다.

 

 

<풀이 및 회고>

이 문제를 처음 보았을때는 시간복잡도가 상당할 것이라고 생각했다. 하지만 문제의 조건에서 볼 수 있듯이 카드의 갯수가 최대 100개밖에 없기 때문에 시간복잡도 측면에서는 걱정할 필요가 없을 것이라고 생각했다. 나랑 성윤님은 이 문제를 보고 가장 먼저 떠오르는 생각을 구체화 해보기로 했다. 그래서 우리는 삼중 for문을 통해 문제를 해결할 수 있다고 생각했고 실제 예시를 들어가며 이 문제를 풀었다.

#첫번째 for문 -> 0
#두번째 for문 -> 1
#세번째 for문 -> 2


#첫번째 for문 -> 0
#두번째 for문 -> 1
#세번째 for문 -> 3

…
#첫번째 for문 -> 0
#두번째 for문 -> 1
#세번째 for문 -> N-1


#첫번째 for문 -> 1
#두번째 for문 -> 2
#세번째 for문 -> 3

#첫번째 for문 -> 1
#두번째 for문 -> 2
#세번째 for문 -> 4

#첫번째 for문 -> 1
#두번째 for문 -> 2
#세번째 for문 -> 5


#첫번째 for문 -> 2
#두번째 for문 -> 3
#세번째 for문 -> 4

#첫번째 for문 -> 2
#두번째 for문 -> 3
#세번째 for문 -> 5
n,m = map(int,input().split())
numList = list(map(int,input().split()))
sum = 0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            cur = numList[i]+numList[j]+numList[k]
            if sum < cur and cur <= m:
                sum = cur
print(sum)

위 주석을 보면 알 수 있듯이 하나하나 예시를 들어가면서 문제를 푼 흔적을 알 수 있다. 이처럼 나는 원래 문제를 풀때 귀납적인 방법으로 문제를 많이 푼다. 즉 예시를 하나하나 들어가면서 규칙성을 발견하는 타입이다.

 

<문제2>

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

 

<풀이 회고>

이 문제 같은 경우에는 처음에 성윤님이랑 고민을 같이 많이 한 문제이다. 왜냐하면 바로 생성자가 없을 경우 때문이다. 만약 생성자가 없다면 0을 출력해야 하는데 어떻게 하면 생성자가 없다는 것을 알 수 있을까 였다. 그래서 나는 for else 구문을 통해서 이 로직을 완성했다.

완성한 코드는 다음과 같다.

 

n = 1
for i in range(1,n+1):
    sum1 = sum(list(map(int,str(i))))
    total = i + sum1
    if n == total:
        print(i)
        break
else: #break 안걸림 -> 생성자가 없음
    print(0)

그리고 다른 방법으로도 이 로직을 구현했다.

n = 1
for i in range(1,n+1):
    sum1 = sum(list(map(int,str(i))))
    total = i + sum1
    if n == total:
        print(i)
        break
	if i == n:
    	print(0)
        break

n = 1
answer = 0
for i in range(1,n+1):
    sum1 = sum(list(map(int,str(i))))
    total = i + sum1
    if n == total:
        answer = i
        break
print(answer)

 

위 방법은 성윤님이 작성한 코드이며 밑에 코드는 승현님이 작성한 코드이다. 난 여기서 승현님이 작성한 코드가 되게 인상적이었다.

왜냐하면 따로 생성자에 대한 로직을 구현하지 않아도 생성자가 0일때를 고려한 문제이기 때문에 되게 인상적이었다.