제일 처음 40분 삽질 (아니 이게 왜 안되냐고 ㅡㅡ )
-> 문제를 잘못 읽었다
"지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나뉘어져 있는 MxN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고~~"
여기까지만 읽고...
테스트 케이스 첫 번째
이거만 보고...
입력이 무조건 정사각형인 줄 알았다. 그렇다 당연히 핑계다. 문제를 끝까지 읽자.
이 단계까지 왔을 때 코드를 적어본다.
mapList = []
M = N = cnt = 0
def inputFunc():
global M,N
M,N = map(int, input().split())
for i in range(0, N):
oneRow = input()
mapList.append(list(oneRow))
# def printFunc():
# for i in range(0, N):
# for j in range(0, M):
# print(mapList[i][j], end='')
# # 줄바꿈 없이 출력하기
# print()
# 입력 확인용 함수
def fillFunc():
global cnt
if mapList[0][0] == 'W':
for i in range(0, N):
for j in range(0, M):
if i % 2 == 0:
# 짝수 로우 일 경우
if j % 2 == 0:
# 짝수 컬럼일 경우
if mapList[i][j] != 'W':
cnt += 1
else:
# 홀수 컬럼일 경우
if mapList[i][j] != 'B':
cnt += 1
else:
#홀수 로우일 경우
if j % 2 == 0:
# 짝수 컬럼일 경우
if mapList[i][j] != 'B':
cnt += 1
else:
# 홀수 컬럼일 경우
if mapList[i][j] != 'W':
cnt += 1
else:
# 시작이 B 일 경우
for i in range(0, N):
for j in range(0, M):
if i % 2 == 0:
# 짝수 로우 일 경우
if j % 2 == 0:
# 짝수 컬럼일 경우
if mapList[i][j] != 'B':
cnt += 1
else:
# 홀수 컬럼일 경우
if mapList[i][j] != 'W':
cnt += 1
else:
#홀수 로우일 경우
if j % 2 == 0:
# 짝수 컬럼일 경우
if mapList[i][j] != 'W':
cnt += 1
else:
# 홀수 컬럼일 경우
if mapList[i][j] != 'B':
cnt += 1
inputFunc()
fillFunc()
print(cnt)문제를 잘못 읽었구나 라는 걸 인지함과 동시에 이게 그래도 틀렸다는 걸 알아차렸다.
구한 교체 횟수가 어떻게 최소의 교체 숫자임을 보장할 수 있나?
예외는 다음과 같다.
첫 번째 칸만 바꿔서 최소가 될 수 있는 경우가 있다.
그래서 코드를 다시 짰다.
첫 번째 칸을 W로 했을 때 교체 횟수와 B로 했을 때 교체 횟수를 나눠서 각각을 구한 다음 이를 비교해서 최소값을 출력해준다.
이 때까지 무조건 맞다고 생각했는데 런타임 에러가 나왔다. 문제를 잘못 읽은 것이다. 입력은 정사각형이 아닐 수 있고 주어진 입력에서 8x8으로 잘랐을 때 최소가 될 수 있는 교체 횟수를 구하는 것이였다.
다시 코드를 짰다. 칸마다 함수를 돌리고(W로 시작했을 때의 교체 횟수와 B로 시작했을 때의 교체 횟수를 비교하여 최소값을 구하는 과정) 근데 지금까지는 머리부터 박고 구현부터 하는 걸 제일 잘했으면서 정말 갑자기 시간 복잡도는 어떻게 되지? 이게 말이 되나? 라는 생각을 했다.
시간이 너무 오래 걸릴 것 같았다. 더 괜찮은 알고리즘이 있는데 내가 모르는 건 아닐까?라는 생각이 계속 들었다.
하노이 탑 때문이다 분명히
그래서 정현이 형한테 조언을 구했다. 이렇게 이렇게 구할거고 이렇게 하면 분명히 정답일거 같은데 이게 시간이 넘치진 않을까요?
파이썬이여서 더 쫄았던거 같다
결론은 시간 제한은 걸리지도 않을 뿐더러 넉넉하기까지 하다.
mapList = []
M = N = cnt = 0
def inputFunc():
global M,N
# 13, 10
# 첫 번째 줄에 13
N,M = map(int, input().split())
for i in range(0, N):
oneRow = input()
mapList.append(list(oneRow))
# def printFunc():
# for i in range(0, N):
# for j in range(0, M):
# print(mapList[i][j], end='')
# # 줄바꿈 없이 출력하기
# print()
# 입력 확인용 함수
def checkFunc():
answerList = []
for i in range(0, N):
for j in range(0, M):
if i <= N - 8 and j <= M - 8:
startFromW = startFromWFunc(i, j)
startFromB = startFromBFunc(i, j)
if startFromW > startFromB:
# print("choose startFromB because ", "startFromW = ",startFromW, "startFromB = ", startFromB)
# print("i = ", i, " j = ", j, startFromB)
answerList.append(startFromB)
else:
# print("choose startFromW because ", "startFromW = ",startFromW, "startFromB = ", startFromB)
# print("i = ", i, " j = ", j, startFromW)
answerList.append(startFromW)
answerList.sort()
print(answerList[0])
# W로 시작한다고 했을 경우의 값
def startFromWFunc(startrow, startcol):
global cnt
cnt = 0
for i in range(startrow, startrow + 8):
if i % 2 == 0:
# 짝수 로우 일 경우
for j in range(startcol, startcol + 8):
if j % 2 == 0:
# 짝수 컬럼일 경우
if mapList[i][j] != 'W':
cnt += 1
else:
# 홀수 컬럼일 경우
if mapList[i][j] != 'B':
cnt += 1
else:
#홀수 로우일 경우
for j in range(startcol, startcol + 8):
if j % 2 == 0:
# 짝수 컬럼일 경우
if mapList[i][j] != 'B':
cnt += 1
else:
# 홀수 컬럼일 경우
if mapList[i][j] != 'W':
cnt += 1
return cnt
def startFromBFunc(startrow, startcol):
global cnt
cnt = 0
for i in range(startrow, startrow + 8):
if i % 2 == 0:
# 짝수 로우 일 경우
for j in range(startcol, startcol + 8):
if j % 2 == 0:
# 짝수 컬럼일 경우
if mapList[i][j] != 'B':
cnt += 1
else:
# 홀수 컬럼일 경우
if mapList[i][j] != 'W':
cnt += 1
else:
#홀수 로우일 경우
for j in range(startcol, startcol + 8):
if j % 2 == 0:
# 짝수 컬럼일 경우
if mapList[i][j] != 'W':
cnt += 1
else:
# 홀수 컬럼일 경우
if mapList[i][j] != 'B':
cnt += 1
return cnt
inputFunc()
checkFunc()최악의 경우(입력이 50 50 일 경우)에 42번째까지 갔다가 안에 맵을 다 돌면서 확인을 해야 하고 이 때에도 B로 시작할 지 W로 시작할 지를 계산해서 최소값을 찾아야 하므로
이 경우 시간 복잡도는 대략 (42x42)x(8x8x2) 이다.
제출을 했으나 정답이 나왔고 수행시간 112ms(0.112s)가 나왔다. 시간 제한은 2초였다.
충분했을 뿐 아니라 넉넉하기까지 하다. 괜히 쫄았던것 같다.
이번 문제의 조언은.. 좀 짜치긴 하지만?
말도 안되게 시간이 오래 걸리는 경우 말고는 정답 자체가 단순 브루트 포스로 푸는 것일 수 있으니 일단 구현부터 해보고 제출먼저 해보자.
