[5문제] 완전 탐색 문제풀이 01

완전 탐색 유형은 모든 경우의 수를 다 해보아야 하는 유형이다. 주어진 문제의 요구를 구현할 수 있는 능력이 중요한 것 같다.

백준 2501번

해결 아이디어

n,k 값을 받고 for문을 n만큼 돌려서 1~n까지의 수로 n을 나누는 작업을 했다. 나머지가 0일 경우, n의 약수이므로 리스트에 따로 담아둔다. 그 후, 리스트에서 k번째로 작은 약수를 출력하기 위해서 인덱스가 k-1인 (인덱스는 0부터 시작하므로) 리스트 요소를 뽑아준다.

내가 작성한 코드

n, k = map(int,input().split(' '))
lst =[]

for i in range(1,n+1):
    if n % i == 0:
        lst.append(i)

if len(lst) < k:
    print(0)
else:
    print(lst[k-1])

백준 16561번

해결 아이디어

n이 9(3x3)일 때는 방법의 개수가 1개이다.
n이 12(3x4)일 때는 방법의 개수가 3개이다.
n이 15(3x5)일 때는 방법의 개수가 6개이다.
n이 18(3x6)일 때는 방법의 개수가 10개이다.
1은 1이고, 3은 1+2, 6은 1+2+3, 10은 1+2+3+4 이므로 이러한 규칙성을 일반화시켜보면, n // 3을 k라고 할 때 방법의 개수는(k-2)*(k-3)/2이다.

내가 작성한 코드

n = int(input()) // 3
result = int((n-1)*(n-2)/2)
print(result)

백준 2798번

해결 아이디어

3장을 a,b,c라고 할 때, 모든 경우의 수를 계산해서 M보다 작은 값들 중에서 최댓값을 출력하도록 하였다.

내가 작성한 코드

import sys

n, m = map(int,sys.stdin.readline().split(' '))
cards = list(map(int,sys.stdin.readline().split(' ')))
result = []

for a in range(0,n-2):
    for b in range(a+1, n-1):
        for c in range(b+1, n):
             sum_cards = cards[a] + cards[b] + cards[c]
             if sum_cards <= m:
                result.append(sum_cards)

print(max(result))

백준 2231번

해결 아이디어

문제에서 요구하는 조건 그대로 구현하였다. 2가지 방법으로 풀었다. 한 가지 방법은 이중 for문으로 해결했고, 다른 한 가지 방법은 각 자리 수의 합을 리스트로 받아주는 방법이었다.

뒤에 풀었던 방법은 미처 생각하지 못한 방법이라서 배울 수 있었다. 내가 파이썬을 효율적으로 사용하는 느낌이었다. 확실히 이중 for문보다 시간도 단축되고 길이도 줄어드는 효율적인 코드였다.

내가 작성한 코드 - 방법1

number = input()

for i in range(1,int(number)+1):
    each_num_sum = 0
    i = str(i)
    for j in range(len(i)):
        each_num_sum += int(i[j])
        div_sum = int(i) + each_num_sum
    if div_sum == int(number):
        print(int(i))
        break
    elif int(i) == int(number):
        print(0)

내가 작성한 코드 - 방법2

number = int(input())
result = 0
for i in range(1, number+1):
   each_num_lst= list(map(int, str(i)))  # 각 자리 수를 리스트에 담는다.
   div_num = i + sum(each_num_lst)
   if div_num == number:
       print(i)
       break
   if i == number:
       print(0)

백준 2309번

해결 아이디어

마찬가지로 문제에서 요구하는 조건들을 그대로 구현해주었다. 결국엔 모든 경우를 탐색해야하는 문제이기는 하나, 난쟁이 7명을 찾는 것이 아닌 난쟁이가 아닌 두 명을 찾아서 빼주는 방법으로 해결했다.

내가 작성한 코드

dwarf = [int(input()) for _ in range(9)]
not_dwarf1, not_dwarf2 = 0,0
first_break = True
        
for i in range(9):

   if first_break == False:
       break
   
   for j in range(1,8):        
       not_dwarf = dwarf[i]+dwarf[j]
       if sum(dwarf) - not_dwarf == 100:
           not_dwarf1 = dwarf[i]
           not_dwarf2 = dwarf[j]
           first_break = False    
           break
      
dwarf.remove(not_dwarf1)
dwarf.remove(not_dwarf2)
dwarf = sorted(dwarf)

print('\n'.join(map(str,dwarf)))