https://www.acmicpc.net/problem/3085
3085번: 사탕 게임예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.www.acmicpc.net
와 나는 알고리즘생각하느라 잠을못잘뻔했는데
알고보니 그딴거없이 하나씩 다 해보는게 브루트포스였다.
먼져, 2차원 보드에서 연속되는 값의 최댓값을 셀 함수 check(board) 를 만든다.
모든 행, 열 을 비교하며 가장 많이 연속되는 값의 개수를 리턴한다..
메인에서
우리는 굳이 4방향을 다 바꿀 필요 없이, 각 원소의 오른쪽과 아래만 바꾸면 모든 경우를 다 시험 가능하다.
각 행, 열의 마지막 원소는 바꿀 필요 없으므로 예외처리를 한다.
먼져, 모든 원소의 오른쪽 원소와 바꿔가며, 그 상태에서의 연속되는 수를 센다.(check)
그 후 바꾼 원소를 제자리에 돌려놓는는다.
그 후, 모든 원소의 아래쪽 원소와 바꿔가며, 그 상테에서 연속되는 수를 센다.(check)
그 후 제자리에 놓는다.
각각의 check값을 리턴하여, 가장 큰 수를 구하면 된다.
1시간정도 계속 코드를 짰는데 계속 틀렸습니다가 나오는 바람에, 너무 화가나서 정답 코드랑 비교해봤더니,
변수이름 하나에 r이 붙어있었다. 그거잡을려고 40분동안 뻘짓한듯 하다.
##코드##
def check(board): n=len(board) answer=1 for i in range (n):
cnt=1 for j in range(1,n): #열탐색
if board[i][j]==board[i][j-1]: cnt+=1
else: cnt=1 if cnt>answer:
answer=cnt cnt=1
for j in range(1,n): #행탐색 if board[j][i]==board[j-1][i]:
cnt+=1 else: cnt=1
if cnt>answer: answer=cnt
return answer n=int(input())board=[]
board=[list(input())for _ in range(n)]real_ans=0for i in range(n):
for j in range(n): if i+1<n: #i+1에서 오류방지 # 오른쪽과 바꿈
board[i][j],board[i+1][j]=board[i+1][j],board[i][j]
temp=check(board) # 탐색하여 최댓값구함 if temp>real_ans:
real_ans=temp #이전최댓값보다 크면 갱신
board[i][j],board[i+1][j]=board[i+1][j],board[i][j]
#보드 초기화 if j+1<n: #j+1에서 오류방지 #아랫쪽과 바꿈
board[i][j],board[i][j+1]=board[i][j+1],board[i][j]
temp=check(board) if temp>real_ans: #위와 동일
real_ans=temp real_ans=max(check(board),real_ans)
board[i][j],board[i][j+1]=board[i][j+1],board[i][j]
#보드 초기화 print(real_ans)