14. [12단계] 제목: 브루트 포스 (1~2챕터)

브루트 포스에 대한 공부는 다음 포스팅을 참고하자.

https://codingworld2002.tistory.com/107

브루트 포스 알고리즘

---

1단계.
딜러는 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장의 합을 출력한다.

답: 

N, M = map(int, input().split())
arr = list(map(int, input().split()))
result = [] #배열 추가용
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            three =  arr[i] + arr[j] + arr[k]
            if (three > M):
                continue
            else:
                result.append(three)
print(max(result))

먼저 n과 m를 입력받는다. 이후 배열 하나를 만들어 낸다. 이 배열을 이용해서 모든 경우의 수인 (3개)를 찾아낼 것이다.

경우의 수가 3개이니 for문은 3개가 나와줘야 할 것이다.

이후 모든 n까지의 i,j,k의 배열이 three라는 결과값으로 들어간다. m은 최대치이니 모든 배열 합이 m보다는 작아야 한다.

그게 아니라면 빈 배열인 result에 three를 추가해준다.

for문이 전부 끝나게 되면 result에 값이 저장되고, max 함수를 이용해서 최댓값을 프린트하면 된다.

---

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을 출력한다.

답:

n = int(input())  
for i in range(1,n+1):   # 해당 분해합의 생성자 찾기
    num = sum((map(int, str(i))))  # i의 각 자릿수를 더함
    num_sum = i + num  
    if (num_sum == n):
        print(i)
        break
    if (i == n):  
        print(0)

n을 입력받는다. 이후 1부터 n까지 for문을 돌린다.

i는 1부터 n이 될 것이며 이 자릿수를 합해서 기입한다. 모든 자릿수를 sum함수로 합치고 num에 넣어준다.

생성자는 일단 숫자 전체와 그 숫자의 자릿수들을 다 합 한 것이기에, 이미 합쳐진 num과 생성자를 합을 num_sum에 넣어준다.

이후 만일 num_sum과 입력받은 n이 같으면 가장 마지막인 n을 출력하게 된다. (for문으로 해석하면 i를 출력하는 셈.)

이후 break로 for문을 탈출해 준다. 만일 그게 아니고 생성자가 없는 경우.(예를 들어 마지막 값과 입력받은 n이 같으면) 0을 출력하게 만든다.

참고로 생성자는 i이며 i와 입력값 n이 같으면 생성자가 없다는 뜻과 같다.