https://www.acmicpc.net/problem/1018
1018번: 체스판 다시 칠하기
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
> 브루트포스
만약 입력된 사각형이 9*9라면 우리는 다음과 같은 방식으로 총 네가지 경우에서 바꿔 칠해야하는 사각형의 개수를 구해야한다.
반복해야 할 수는 각각 n-7, m-7번이라는 것을 알 수 있다.
4가지 경우에서 W로 시작하는 패턴, B로 시작하는 패턴, 이 두가지 경우의 패턴에 대해 모두 테스트해야한다.
나 같은 경우엔 그냥 반복해야하는 문자열 패턴을 pat1, pat2로 설정해놓고 점검해야하는 행 수가 짝수인 경우 패턴의 0번째 문자열과 비교를, 홀수인 경우 패턴의 1번째 문자열과 비교하여 문자가 다른 경우(바꿔칠해야하는 경우) val1과 val2에 각각 1씩 더해주었다. 두 수를 반복문이 끝날 때 result 리스트에 넣은 후, 모든 점검이 끝났을 때 리스트에서 최솟값을 꺼내 출력하면 완성이다.
위 알고리즘을 구현하면 다음과 같다.
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| [프로그래머스 | 파이썬3] 약수의 개수와 덧셈 (0) | 2021.12.09 |
|---|---|
| [프로그래머스 | 파이썬3] 실패율 - 정렬 (0) | 2021.12.08 |
| [백준 | 파이썬3] 1541. 잃어버린 괄호- 그리디알고리즘 (2) | 2021.12.06 |
| [백준 | 파이썬3] 10866 덱 - 덱 (1) | 2021.12.02 |
| [백준 | 파이썬3] 1181. 단어정렬 - 정렬 (2) | 2021.12.02 |