★BF Upper-Beginner I - 16 Solved★

★ 2798 블랙잭 ★

 

from itertools import combinations

N,M = map(int, input().split())
cards = list(map(int,input().split()))
groups = list(combinations(cards,3))
sum_of_group = []

for group in groups:
    sum_of_group.append(sum(group))

sum_of_group.sort(reverse=True)

for sum_of_group_each in sum_of_group:
    if sum_of_group_each <= M:
        print(sum_of_group_each)
        break

 

- 풀이 1 - (combinations 조합 함수를 이용한 모든 경우의 수 순회)

🗽 combinations(cards,3) 함수를 이용해서 중복없이 3장의 카드를 뽑는 가짓수를 모두 구할 수 있다.

🗽 각각의 가짓수 중 M에 최대한 맞는 경우의 수(모든 경우의 수에 관해 순회 - brute-force)를 찾으면 끝

 

- 풀이 2 - (for문 세 번)

🗽 for문을 세 번 돌림으로써, combinations 함수 사용없이 리스트의 모든 케이스를 가져와 판단하는 brute-force를 시행

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

for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if cards[i] + cards[j] + cards[k] > M:
                continue
            else:
                res = max(res,cards[i] + cards[j] + cards[k])
print(res)

 

🗽 여기서, for문에 값 자체를 안돌리고, index를 돌려 indexing을 사용하였음을 기억: 코드 출처

---

★ 2231 분해합 ★

 

N = int(input())

l = len(str(N))
yes = 0
if (N-l*9) < 0:
    start = 1
else:
    start = N-l*9

for num in range(start,N): 
    each_sum = 0
    for each in list(str(num)):
        each_sum+=int(each)

    if num + each_sum == N:
        print(num)
        yes+=1
        break

if yes != 1:
    print(0)

 

🗽 전형적인 brute-force 알고리즘 - 조건에 부합하는 지 범위를 모두 탐색하기에 - 관건은 코드 작동 시간을 최대한으로 줄이는 방법

 

🗽 ① 생성자가 가능한 범위를 최대한 좁힌다

▶ N에서 len(N)*9를 뺀 그 사이의 범위가 생성자 판단 가능 범위!

▶ 이 범위를 벗어나면 애초에 생성자 생성이 안되기에 brute-force 탐색 범위를 최소화.

(만약 0보다 작다면 1부터 시작하게 설정)

 

🗽 ② 가장 작은 생성자를 구해내는 프로그램이니, 범위의 가장 최솟값부터 시작해, 생성자가 발견되면 바로 break 걸어 코드 작동 시간 최소화

▶ 도중에 원하는 답을 구했다면, 더 탐색 필요없이 바로 답을 출력하게 하고 break문을 걸어 loop 작동을 멈춘다.

 

🗽 ③ yes 변수를 활용해, 구했다면 1, 아닐 경우 쭉 loop을 돌아 0으로 값이 변하지 않기에, 최종적으로 yes 변수 판정으로 0을 출력하게 함

---

★ 25494 단순한 문제 (Small) ★

 

🗽 문제 그대로 1부터 자기자신까지 각각 모든 경우의 수를 살피는 3중 for문 - brute-force로 풀어도 된다

for _ in range(int(input())):
    a,b,c=map(int,input().split())
    cnt = 0
    for i in range(1,a+1):
        for j in range(1,b+1):
            for k in range(1,c+1):
                if i%j == j%k == k%i:
                    cnt += 1
    print(cnt)

 

◆ brute-force 이외 풀이 ◆

 

🗽 수학문제로, 왜 a=b=c인 경우만 답이 되는 지, 증명해보면

① a < b < c

② a < b = c

③ a = b = c

 

①>

→ a mod b = a (b가 a보다 크므로)

→ b mod c = b (c가 b보다 크므로)

∴ 따라서, a mod b인 결과와 b mod c인 결과가 서로 같아야 하므로, a와 b가 같다는 결론이 나와 모순! a<b<c가 될 수 없다

 

②>

→ a mod b = a

→ b mod c = 0 (b와 c가 같으므로 나머지는 0)

∴ 따라서, a mod b인 결과와 b mod c인 결과가 서로 같게 되므로, 즉, a는 0이라는 결론이 나와 모순!

(a,b,c 모두 1이상의 자연수라는 전제가 문제에 있으므로)

 

③>

→ a mod b = 0

→ b mod c = 0

→ c mod a = 0

∴ 유일하게 ③이 성립!

 

∴ 따라서, 세 수가 모두 같은 경우의 수는 세 수 중 최솟값 자체를 뜻하므로, min()만 돌리면 바로 답이 나온다

for _ in range(int(input())):
    print(min(map(int,input().split())))

 

(일일이 다 돌리는 brute-force이므로 소요 시간에도 차이가 난다)

---

★ 1526 가장 큰 금민수 ★

 

def is_gumminsu(num):
    x = {'4','7'}

    for ch in str(num):
        if ch not in x:
            return False
    
    return True

N = int(input())

for n in range(N,3,-1):
    if (n%10 == 4) or (n%10 == 7):  
        if is_gumminsu(n):
            print(n)
            break

 

🗽 brute-force 풀이의 핵심은 '시간단축' - 모든 경우의 수를 순회하기에 최대한 시간이 덜 걸리는 쪽으로 장치를 많이 만들어 놓아야 좋다.

 

🗽 코드 설명>

① 4와 7로만 구성되므로 10으로 나눈 나머지가 4와 7이 아닌 경우는 함수를 거치지 않고 바로 pass 하게 만듦

② pass되지 않은 경우 is_gumminsu 함수로 이동 → 맨 앞자리부터 4나 7이 아닐 경우 바로 False 리턴

---

★ 16861 Harshad Numbers ★

 

n=int(input())
while 1:
    total=0
    for i in range(len(str(n))):
        total+=int(str(n)[i])
    if n%total==0:
        print(n)
        break
    n+=1

 

🗽 n값을 1씩 증가하면서 harshad number에 해당되는 지 계속 확인하면 끝!

---

★ 24807 Math Homework ★

 

b,c,d,l=map(int,input().split())
y=0
for i in range(l//b+1):
    for j in range((l-i*b)//c+1):
        for k in range((l-i*b-j*c)//d+1):
            if (i*b+j*c+k*d)==l:
                y+=1
                print(i,j,k)
if y==0:print('impossible')

 

🗽 b - c - d 차례대로 각각 0부터 전체 l로 나눈 몫까지 돌면서 (c는 b가 차지한 부분 제외한 범위까지, d는 b와 c 둘 다 차지한 부분 제외한 범위까지 - 범위를 그렇게 안 잡아도 되지만 brute-force이므로 소요 시간 최소화를 위해 끝 범위를 잡아줌) 합이 l과 같은 지 비교, 맞다면 바로 출력!

 

🗽 모든 경우의 수를 돌면서 l과 같은 지 비교하므로 brute-force 기초 유형

---

★ 6131 완전 제곱수 ★

 

N=int(input())
ans = 0
for i in range(1,500):
    num = i**2 + N
    if num**(1/2)>500:break
    if num**(1/2) == int(num**(1/2)):ans+=1
print(ans)

 

🗽 499까지 일일이 검사 (500은 답이 될 수 없으므로 pass)

 

🗽 여기서 만약 후보 B가 500을 초과한다면 i가 증가하면서 더 이상 완전제곱수는 나올 수 없으므로 break

---

★ 10419 지각 ★

 

for _ in range(int(input())):
    d=int(input())
    ans=0
    while 1:
        if (ans*(ans+1))>d:
            print(ans-1)
            break
        ans+=1

 

🗽 BF로 일일이 ans의 값을 증가시켜  s(s+1)의 결과가 d를 넘을 때 까지 확인

---

★ 15667 2018 연세대학교 프로그래밍 경진대회 ★

 

N=int(input())
K=1
while 1:
    if (1+K+K**2)==N:
        print(K)
        break
    K+=1

 

🗽 후보가 될 수 있는 K를 1부터 차례대로 1씩 증가시켜 주어진 방정식 $K^2 + K + 1 = N$을 만족시키면 답 출력하고 끝!

 

🗽 또는 $K^2 + K + 1 = N$을 K에 대한 이차방정식으로 풀어 K 관련 해를 근의 공식 결과로 대입할 수도 있다.

print(int(((4*int(input())-3)**(1/2)-1))//2)

---

★ 9094 수학적 호기심 ★

 

import sys
input=sys.stdin.readline
for _ in range(int(input())):
    n,m=map(int,input().split())
    cnt=0
    for i in range(1,n-1):
        for j in range(i+1,n):
            if (i**2+j**2+m) % (i*j) == 0:
                cnt+=1

    print(cnt)

 

🗽 중첩 for loop을 통해 일일이 검사하며 분자를 분모로 나눈 나머지가 0인지 확인!

---

★ 4690 완전 세제곱 ★

 

for a in range(6,101):
    for b in range(2,100):
        for c in range(b,100):
            for d in range(c,100):
                if a**3 == b**3 + c**3 + d**3:
                    print(f'Cube = {a}, Triple = ({b},{c},{d})')

 

🗽 완전 세제곱 방정식이 맞는 지 일일이 확인하기 위해 for문으로 차례대로 확인

---

★ 19532 수학은 비대면강의입니다 ★

 

import sys
a,b,c,d,e,f=map(int,input().split())

for x in range(-999,1000):
    for y in range(-999,1000):
        if ((a*x+b*y)==c) and ((d*x+e*y)==f):
            print(x,y)
            sys.exit()

 

🗽 일일이 -999부터 999까지 x와 y를 놓고 돌려 맞다면 바로 출력하고 종료! 전형적인 BF 유형

---

★ 1075 나누기 ★

 

N=input().rstrip()
F=int(input())

for i in range(100):
    if i<10:n=int(N[:-2]+'0'+str(i))
    else:n=int(N[:-2]+str(i))
    if n%F==0:
        if i<10:print('0'+str(i))
        else:print(i)
        break

 

🗽 00부터 99까지 일일이 확인

---

★ 3040 백설 공주와 일곱 난쟁이 ★

 

from itertools import combinations
hats=[int(input().rstrip())for _ in range(9)]
total=sum(hats)
for x in list(combinations(hats,7)):
    if sum(x) == 100:
        print(*list(x),sep='\n')
        break

 

🗽 combinations의 결과를 list()로 list로 만들어주어야 반복문 돌아감

🗽 tuple을 list()를 활용해 list로 바꿀 수 있음

---

★ 2309 일곱 난쟁이 ★

 

from itertools import combinations
N=[int(input())for _ in range(9)]
l=list(combinations(N,7))
for x in l:
    if sum(x) == 100:
        print(*sorted(list(x)),sep='\n')
        break

---

★ 10448 유레카 이론 ★

 

import sys
from itertools import product
input=sys.stdin.readline
T=[(i*(i+1))//2 for i in range(1,45)]
sums=[]
for pair in product(T,repeat=3):
    sums.append(sum(pair))

for _ in range(int(input())):
    K=int(input())
    if K in sums: print(1)
    else: print(0)

 

🗽 후보 삼각수를 모두 모으고 중복순열의 repeat = 3인자로 가능한 삼각수의 모든 합 구함(BF)

---