백준 알고리즘 10단계 (브루트포스)

  • 새롭게 배운 내용

브루트 포스 알고리즘이란

모든 경우의 수를 탐색하여 요구 조건에 충족하는 결과만을 가져오는 알고리즘이다. ( 쉽게 말해 모든 영역을 전체 탐색한다.)
출처: https://go-coding.tistory.com/67

1) 2798번 블랙잭

주어진 카드들 중 임의로 3장을 골라 M에 가장 가까운 결과를 출력하는 것

N, M = map(int, input().split())
Nums = list(map(int, input().split()))
#결과물을 담을 리스트
ans_list = []

# 3중 반복을 통해 전체 탐색.
for i in Nums:
    for j in Nums[Nums.index(i) + 1:]:
        for k in Nums[Nums.index(j) + 1:]:
            if i + j + k > M:
                continue
            else:
                ans_list.append(i + j + k)

print(max(ans_list))

2) 2231번 분해합

N = int(input())
ans_list = []

for i in range(N):
    num = i
    i_list = list(str(i))
    for j in i_list:
        num += int(j)

    if num == N:
        ans_list.append(i)

if len(ans_list) != 0:
    print(min(ans_list))
else:
    print(0)

3) 7568번 덩치

N = int(input())
student_list = []
ans_list = []
for i in range(N):
    student = list(map(int, input().split()))
    student_list.append(student)

for j in student_list:
    rank = 1
    for k in student_list:
        if j[0] < k[0] and j[1] < k[1]:
            rank += 1
        else:
            continue
    ans_list.append(rank)

answer = ''
for rnk in ans_list:
    answer += str(rnk) + ' '
print(answer[:-1])

4) 1018번 체스판 다시 칠하기

N, M = map(int, input().split())
# 입력한 행, 열 범위의 2차원 배열 생성
all_list = [['B' for col in range(M)] for row in range(N)]

for k in range(N):
    row = input()
    # 입력한 행 값을 위에서 만든 2차원 배열에 넣어줌
    for t in range(M):
        all_list[k][t] = [row[t]]

# 각 경우 마다 바꿔야 되는 횟수를 저장하는 리스트
cnt_list = []
# 시작점의 좌표는 N,M에서 8을 빼고 1을 더해준 만큼의 범위로 설정된다.
for x in range(N-7):
    for y in range(M-7):
        first = all_list[x][y]
        cnt = 0
        해당 시작점을 기점으로 첫번 째 [0][0] 칸의 색을 바탕으로 계산해주고, 이를 cnt_list에 담아준다.
        for i in range(8):
            for j in range(8):
                if i % 2 == 0 and j % 2 == 0 and all_list[x + i][y + j] != first:
                    cnt += 1
                elif i % 2 == 0 and j % 2 != 0 and all_list[x + i][y + j] == first:
                    cnt += 1
                elif i % 2 != 0 and j % 2 == 0 and all_list[x + i][y + j] == first:
                    cnt += 1
                elif i % 2 != 0 and j % 2 != 0 and all_list[x + i][y + j] != first:
                    cnt += 1
        cnt_list.append(cnt)
		
        # 첫번 째 칸의 색을 바꿀 경우 또한 고려한다. (cnt는 1로 초기화한다. 이미 첫번 째 색을 바꿨기 때문.)
        cnt = 1
        if first == ['B']:
            all_list[x][y] = ['W']
        else:
            all_list[x][y] = ['B']
        first = all_list[x][y]
        for i in range(8):
            for j in range(8):
                if i % 2 == 0 and j % 2 == 0 and all_list[x + i][y + j] != first:
                    cnt += 1
                elif i % 2 == 0 and j % 2 != 0 and all_list[x + i][y + j] == first:
                    cnt += 1
                elif i % 2 != 0 and j % 2 == 0 and all_list[x + i][y + j] == first:
                    cnt += 1
                elif i % 2 != 0 and j % 2 != 0 and all_list[x + i][y + j] != first:
                    cnt += 1
        cnt_list.append(cnt)

# 모든 경우의 수를 담아준 리스트에서 최솟값을 출력한다.
print(min(cnt_list))

5) 1436번 영화감독 숌

N = int(input())
cnt = 0
ans = 666

# 입력한 N번 째 숫자를 얻을 때 까지 반복문을 돌려준다.
# 단 1씩 더해가기 때문에 모든 경우의 수를 다 체크한다.
while True:
    if '666' in str(ans):
        cnt += 1
    if cnt == N:
        print(ans)
        break
    ans += 1

좋은 웹페이지 즐겨찾기