• 완전탐색이란? 구현 유형 中 ‘모든 경우의 수를 주저 없이 다 계산하는 해결 방법’
• Leetcode에는 brute force category가 없어서 백준에서 문제를 가져왔습니다.

1. 워밍업...ㅈㅅ (난이도: Easy)

2309번: 일곱 난쟁이

접근 방식

1. 9명 중 7명을 골라서 합이 100인지 모든 경우의 수를 살펴보기
2. 반대로 2명을 제외하면 합이 100이 된다는 것을 이용하기
   1. 조합(Combination)의 개념 이해

Solution

• 7개를 뽑아서 합을 구하는게 뭔가 너무 복잡하게 느껴짐
• 두개를 뽑은 것의 합을 전체 합에서 빼주는 방법으로 코드를 짬

# Solution 1

n = 9
liar1, liar2 = 0, 0
dwarfs = [int(input()) for _ in range(n)]

for i in range(n):
    for j in range(i+1, n):
        if sum(dwarfs) - (dwarfs[i] + dwarfs[j]) == 100:
            liar1 = dwarfs[i]
            liar2 = dwarfs[j]

dwarfs.remove(liar1)
dwarfs.remove(liar2)

#dwarfs.sort()
#for i in range(len(dwarfs)):
#    print(dwarfs[i])

print("\n".join(map(str, sorted(dwarfs))))

2. 문제 풀어보기 (난이도: 위에보다는 어려운 Easy)

1018번: 체스판 다시 칠하기

접근 방식

1. 8 X 8 범위만큼 가능한 모든 경우의 수를 검사한다

2. 잘못 칠해진 개수를 체크한다

3. 검정으로 시작할 때와 흰색으로 시작할 때 2가지 경우 고려

   

4. 최소값을 return 한다

   

처음에 W로 시작하는 체스판이랑 B로 시작하는 체스판을 따로 나누어서 풀어보려고 했으나, 잘되지 않았고, 좌표의 합이 짝수인지 홀수인지로 나누어 W/B을 나누는 것이 훨씬 효율적임을 알게되었습니다.

Solution 1

• 4중 for문 이용
• 행과 열의 합이 짝수인지 홀수인지 구분

# Solution 1

n, m = map(int, input().split()) # nxm 크기 입력 받음
color_chess = [] 
board = [input() for _ in range(n)] # 보드 생성

for i in range(n-7): # n-8인곳까지 자를 수 있지만, index-1이 우리가 원하는 숫자이므로 +1을 해줌
    for j in range(m-7):
        w = 0
        b = 0
        for row in range(i, i+8): # 각 열 모두 체크
            for col in range(j, j+8): 
                if (row+col) % 2 == 0: # 합이 짝수인 경우 (0,0), (0,2), (0,4), (0,6)
                    if board[row][col] != 'W': # 흰색: 다시 칠해야 하는 개수 세기 
                        w = w + 1 
                    if board[row][col] != 'B': # 검은색: 다시 칠해야 하는 개수 세기 
                        b = b + 1
                else:  # 합이 홀수인 경우 (1,0), (1,3), (1,5), (1,7)
                    if board[row][col] != 'W':
                        b = b + 1 # 위에서 짝수인 경우가 w이면 홀수인 경우에 b이 되어야 함. 
                    if board[row][col] != 'B':
                        w = w + 1 # 반대로 짝수인 경우가 b이면 홀수인 경우는 w가 되어야 함. 
        
        color_chess.append(w) # 흰색 다시 칠해야하는 개수
        color_chess.append(b) # 검은색 다시 칠해야하는 개수

print(min(color_chess))

Solution 2

• 풀이: https://ywtechit.tistory.com/129
• 보통은 다 4중 반복문으로 푸는데, 여기서는 2중 반복문 + 함수로 풀이를 함
• 이해가 완전히 된건 아니어서 함게 이야기해보고 싶음

# Solution 2
# 2중 반복문 + 함수
n, m = map(int, input().split())
chess_W = [[0] * m for _ in range(n)] # 흰색으로 시작하는 체스판
chess_B = [[0] * m for _ in range(n)] # 검은색으로 시작하는 체스판
arr = [list(input()) for _ in range(n)]
cnt = float('inf')
 
def check(a, b): # 
    global cnt
    temp_W, temp_B = 0, 0
    for x in range(8):
        for y in range(8):
            if arr[a + x][b + y] != chess_W[a + x][b + y]:
                temp_W += 1
            if arr[a + x][b + y] != chess_B[a + x][b + y]:
                temp_B += 1
    cnt = min(cnt, temp_W)
    cnt = min(cnt, temp_B)
    return cnt
 
for i in range(n): 
    for j in range(m):
        if not (i+j) % 2:  # not 0 == True // if (i+j)%2==0 이라는 뜻. 
            chess_W[i][j] = 'W'
            chess_B[i][j] = 'B'
        else:
            chess_W[i][j] = 'B'
            chess_B[i][j] = 'W'
 
for i in range(n-7):
    for j in range(m-7):
        check(i, j)
 
print(cnt)