공부하는허딩크 : https://www.youtube.com/live/XxNgKJkVQ-E?feature=shared
문제가 길다.
일단 그림을 그려보았는데 복잡하다.
엄청 고민하다가 일단 배열을 2개(graph, answer)를 정의해 주었다.
graph는 입력값을 받아서 w, b를 표기하는 용도고
answer는 graph[1][1]이 w일때 홀수 인덱스와, 짝수 인덱스에 w를 채우고, 나머지는 b를 채우는 역할이다.
그 이후에 전체를 돌면서 graph와 answer가 값이 다르다면 cnt + 1을 해주는 코드를 만들었다.
<첫번째 시도 : 첫번째 예시는 정답이 나왔는데 두번째 예시는 130이 답이 나오네? >
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[0] * (M+10) for _ in range(N + 10)]
answer = [[0] * (M+10) for _ in range(N + 10)]
cnt = 0
for i in range(1, N + 1):
A = input().strip()
for j in range(1, M + 1):
graph[i][j] = A[j-1]
for i in range(1, 8 + 1):
for j in range(1, 8 + 1):
if graph[1][1] == 'W':
if i % 2 != 0 and j % 2 != 0:
answer[i][j] = 'W'
elif i % 2 == 0 and j % 2 == 0:
answer[i][j] = 'W'
else:
answer[i][j] = 'B'
for i in range(1, N + 1):
for j in range(1, M + 1):
if graph[i][j] != answer[i][j]:
cnt += 1
print(cnt)
<두번째 시도 : graph[1][1]이 b일때 경우를 추가했다. _ 두번째 예시에서 98이 나왔다.>
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[0] * (M+10) for _ in range(N + 10)]
answer = [[0] * (M+10) for _ in range(N + 10)]
cnt = 0
for i in range(1, N + 1):
A = input().strip()
for j in range(1, M + 1):
graph[i][j] = A[j-1]
for i in range(1, 8 + 1):
for j in range(1, 8 + 1):
if graph[1][1] == 'W':
if i % 2 != 0 and j % 2 != 0:
answer[i][j] = 'W'
elif i % 2 == 0 and j % 2 == 0:
answer[i][j] = 'W'
else:
answer[i][j] = 'B'
if graph[1][1] == 'B':
if i % 2 != 0 and j % 2 != 0:
answer[i][j] = 'B'
elif i % 2 == 0 and j % 2 == 0:
answer[i][j] = 'B'
else:
answer[i][j] = 'W'
for i in range(1, N + 1):
for j in range(1, M + 1):
if graph[i][j] != answer[i][j]:
cnt += 1
print(cnt)
문제를 읽고 코드를 만들면서 생각했던게 다시 칠해야 하는 정사각형의 최소의 개수를 구하는 것이다.
내가 사용한 answer를 만들고 graph[1][1]과 비교를 한다면 무조건 [1][1]에서부터 비교를 해야하는 것이기에
문제의 의도와는 다르다고 생각은 했지만, 일단 위에 2가지 코드를 작성했다.
여기서 부터 이제 다시 출발해보자. 예제 2를 보면 내가 작성한 graph[1][1]에서 변경하는 것이 아닌 [1][6]에서 변경하는 것이 변경값을 최소화 하는 길이 보이기는 하는데 이걸 코드로 작성하기가 힘들다.
문제를 다시 파악해보자. (하루가 지남.)
잘때 문제를 복기해보니 마지막 for문을 돌릴때 조건을 어떻게 어떻게 주면 될거 같은 생각이 들었다.
입력값을 받은 graph의 비교되는 시작점 (0,0)에서부터 (x, y)지점 / 해당 (x, y)지점은 answer의 배열을 비교하면서 out of range가 되지 않는 지점을 생각했다.
<세번째 시도 : 역시나 틀렸습니다. : 단, 예제 4만 정답이 31이 아닌 32가 나옴. 마지막 w를 고려 못하네....>
이젠 이판사판이다. 정답을 위해서 answer를 2개로 만들자.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[0] * M for _ in range(N)]
answer = [[0] * 8 for _ in range(8)]
for i in range(N):
A = input().strip()
for j in range(M):
graph[i][j] = A[j]
for i in range(8):
for j in range(8):
if graph[0][0] == 'W':
if i % 2 == 0 and j % 2 == 0:
answer[i][j] = 'W'
elif i % 2 != 0 and j % 2 != 0:
answer[i][j] = 'W'
else:
answer[i][j] = 'B'
if graph[0][0] == 'B':
if i % 2 != 0 and j % 2 != 0:
answer[i][j] = 'B'
elif i % 2 == 0 and j % 2 == 0:
answer[i][j] = 'B'
else:
answer[i][j] = 'W'
#여기에서 graph부분에서 range 벗어나지 않는 내에서 하나씩 돌아가면서 확인해 보면?
cnt_answer = []
for i in range(N - 8 + 1):
for j in range(M - 8 + 1):
cnt = 0
for k in range(8):
for p in range(8):
if graph[k+i][p+j] != answer[k][p]:
cnt += 1
cnt_answer.append(cnt)
print(min(cnt_answer))
<네번째시도 : 정답 : 내가봐도 무식한 코드임>
1. answer1과 answer2를 각각 W로 시작하는 배열과 B로 시작하는 배열을 만든다.
2. 입력받은 배열을 계산해서 out of range가 안되도록 N - 8 + 1 / M - 8 + 1 범위를 만들어 준다.
ㄴ 예를 들어 graph[0][0]에서 시작해서 8 X 8범위를 찾아서 cnt를 구하고, graph[2][2]에서도 cnt를 구해서 범위를 벗어나지 않게끔만 작성해줌
3. graph를 돌면서 answer1과 answer2를 비교해서 각각 cnt를 구해주고 최소 값으로 출력해줌
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[0] * M for _ in range(N)]
answer1 = [[0] * 8 for _ in range(8)]
answer2 = [[0] * 8 for _ in range(8)]
for i in range(N):
A = input().strip()
for j in range(M):
graph[i][j] = A[j]
for i in range(8):
for j in range(8):
if i % 2 == 0 and j % 2 == 0:
answer1[i][j] = 'W'
answer2[i][j] = 'B'
elif i % 2 != 0 and j % 2 != 0:
answer1[i][j] = 'W'
answer2[i][j] = 'B'
else:
answer1[i][j] = 'B'
answer2[i][j] = 'W'
#여기에서 graph부분에서 range 벗어나지 않는 내에서 하나씩 돌아가면서 확인해 보면?
cnt_answer = []
for i in range(N - 8 + 1):
for j in range(M - 8 + 1):
cnt1 = 0
cnt2 = 0
for k in range(8):
for p in range(8):
if graph[k+i][p+j] != answer1[k][p]:
cnt1 += 1
if graph[k+i][p+j] != answer2[k][p]:
cnt2 += 1
cnt_answer.append(cnt1)
cnt_answer.append(cnt2)
print(min(cnt_answer))
실제 정답까지 책상에 앉아 있는 시간은 3시간 가까이 된 것 같은데 자기전, 지하철등에서도 고민했으니 더 오래 걸렸다.
<다른 사람 코드와 비교해보자>
엇. 나도 풀었는데 이해가 안간다......
노트필기 시작. : 아래처럼 그림을 그려보았다. (절대 내가 그림을 그리고 찾은게 아니라 다른 사람 풀이를 보면서 이해한거임)
1. 각 x, y의 값의 합이 짝수 / 홀수에 따라 W와 B가 나뉘는걸 볼 수 있다. => 내가 스스로 풀때는 이 개념을 찾지 못함.
이 개념이라면 아주 쪼~~~금 수월하겠다.
2. 그냥 이렇게 받아서 리스트를 만들어 줘도 배열처럼 인덱싱이 가능하다는 걸 다시 상기함.
answer = []
for _ in range(N):
answer.append(input().strip())
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = []
cnt = []
for _ in range(N):
graph.append(input().strip())
#out of range가 일어나지 않은 범위 내에서 각 칸을 돌면서 모든 경우의 수를 확인해야함
for a in range(N - 7):
for b in range(M - 7):
WBOX = 0 #W로 시작할 경우
BBOX = 0 #B로 시작할 경우
for i in range(a, a + 8):
for j in range(b, b + 8):
if (i + j) % 2 == 0:
if graph[i][j] != 'W':
WBOX += 1
else:
BBOX += 1
else:
if graph[i][j] != 'W':
BBOX += 1
else:
WBOX ++ 1
cnt.append(WBOX)
cnt.append(BBOX)
print(min(cnt))
내가 작성한 코드보다 잘 정리되어 있다.
WBOX += 1 / BBOX +=1 을 할때 조금 헷갈리지만, 천천히 잘 그려보면 답은 나온다.
나중에 다시 풀어봐야겠다.