티어 : Gold 5 시간 제한 : 1 초 메모리 제한 : 128 MB 알고리즘 분류 : 구현, 자료 구조, 시뮬레이션, 덱, 큐
문제
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
입력
첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)
다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.
다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)
다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.
출력
첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
예제 입출력
Algorithm
구현 - 시뮬레이션 1. board를 리스트로 구현 ☞ 사과가 있는 칸은 True, 사과가 없는 칸은 False 2. 현재 뱀의 몸이 닿아있는지 여부가 담긴 snake 리스트 구현 ☞ 몸이 닿아있으면 True, 닿아있지 않으면 False 3. 반복문 1번 돌 때마다 snake의 다음 칸 True, 첫 번째 칸 False ☞ 사과 먹으면 첫 번째 칸 놔두기 4. 반복문 1번 돌 때마다 초 증가 ☞ 초 == x+1이면 c의 방향으로 이동 ☞ 현재 방향 (상, 하, 좌, 우) 저장해두고 상일 때 D이면 우, L이면 좌로 변경 하일 때 D이면 좌, L이면 우로 변경 좌일 때 D이면 상, L이면 하로 변경 우일 때 D이면 하, L이면 상으로 변경 5. 다음 칸의 snake가 True이거나 board 범위 벗어나면 break
Code
import sys
input = sys.stdin.readline
# 현재 방향과 변경할 방향으로 인자로 줬을 때 다음 방향을 return하는 함수
def return_index(index, C):
# 현재 방향이 상인 경우
if index == 0:
# C가 D이면 우로 변경
if C == 'D':
index = -1
# C가 L이면 좌로 변경
else:
index = 2
# 현재 방향이 하인 경우
elif index == 1:
# C가 D이면 좌로 변경
if C == 'D':
index = 2
# C가 L이면 우로 변경
else:
index = -1
# 현재 방향이 좌인 경우
elif index == 2:
# C가 D이면 상으로 변경
if C == 'D':
index = 0
# C가 L이면 하로 변경
else:
index = 1
# 현재 방향이 우인 경우
else:
# C가 D이면 하로 변경
if C == 'D':
index = 1
# C가 L이면 상으로 변경
else:
index = 0
return index
# board 구현
N = int(input())
board = [[False for _ in range(N+1)] for _ in range(N+1)]
# 뱀 리스트 구현
snake = [[False for _ in range(N+1)] for _ in range(N+1)]
# 사과 위치 저장
K = int(input())
for _ in range(K):
x, y = map(int, input().split())
# 사과 위치 True로 변환
board[x][y] = True
# 뱀의 방향 변환 정보 저장
L = int(input())
move = []
for _ in range(L):
time, direction = input().split()
move.append((int(time), direction))
# 방향 : 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
index = -1 # 현재 방향
x = 1 # 현재 위치
y = 1 # 현재 위치
# 현재 위치에 뱀 저장
snake[x][y] = True
snake_length = 1 # 뱀 길이
last_loc = [1, 1]
time = 1
index_record = []
while True:
# 현재 시간이 X+1이면 C의 방향으로 방향 회전
if move and time == move[0][0]+1:
index = return_index(index, move[0][1])
move = move[1:]
# 현재 방향으로 이동
nx = x+dx[index]
ny = y+dy[index]
# 다음 칸의 위치에 뱀의 몸이 있거나 board의 범위를 벗어나면 break
if nx < 1 or nx > N or ny < 1 or ny > N or snake[nx][ny]:
break
index_record.append(index)
# 다음 칸으로 뱀 이동
snake[nx][ny] = True
snake_length += 1
# 사과가 있으면 사과 삭제
if board[nx][ny]:
board[nx][ny] = False
else: # 사과가 없으면 첫 칸에서 뱀 삭제
snake[last_loc[0]][last_loc[1]] = False
snake_length -= 1
last_loc[0] += dx[index_record[-snake_length]]
last_loc[1] += dy[index_record[-snake_length]]
# 시간 증가
time += 1
# x, y 갱신
x = nx
y = ny
print(time)
티어 : Gold 5 시간 제한 : 2 초 메모리 제한 : 512 MB 알고리즘 분류 : 구현, 문자열, 그리디 알고리즘
문제
수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.
이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.
문자열의 뒤에 A를 추가한다.
문자열을 뒤집고 뒤에 B를 추가한다.
주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)
출력
S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.
예제 입출력
Algorithm
완전 탐색 이용 1. T에서 가장 맨 뒤에 A가 있다면 A 빼기 2. T에서 가장 맨 뒤에 B가 있다면 B 빼고 reverse 3. 1, 2 과정 후 S와 동일한지 확인 4. T의 길이가 0이 되면 BREAK
Code
import sys
input = sys.stdin.readline
S = input().rstrip()
T = input().rstrip()
answer = '0'
while T:
# T의 가장 맨 뒤에 A가 있다면 A 빼기
if T[-1] == 'A':
T = T[:-1]
else: # T의 가장 맨 뒤에 B가 있다면 B 빼고 reverse
T = T[:-1]
T = T[::-1]
# T의 값이 S와 같으면 break
if T == S:
answer = '1'
break
print(answer)
티어 : Gold 5 시간 제한 : 2 초 메모리 제한 : 512 MB 알고리즘 분류 : 구현, 브루트포스 알고리즘
문제
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
입력
첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.
예제 입출력
Algorithm
완전 탐색 이용 1. 테트로미노의 모든 경우의 수마다 도느 좌표의 합을 구해 최댓값 갱신 ☞ 테트로미노마다 회전과 대칭을 고려해야 함
고려해야 하는 경우의 수가 총 19개 1. 파란색 도형 : 90도 회전 2. 노란색 도형 : 고려할 변형 도형 없음 3. 주황색 도형 : 90도 회전, 180도 회전, 270도 회전, 90도 회전 후 상하대칭, 90도 회전 후 좌우대칭, 상하대칭, 좌우대칭 4. 초록색 도형 : 90도 회전, 90도 회전 후 좌우대칭, 상하대칭 5. 분홍색 도형 : 90도 회전, 180도 회전, 270도 회전
모든 케이스의 반례를 공유해놓은 글이 있어 많은 도움이 되었다. https://www.acmicpc.net/board/view/61597
Code
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
board = []
for _ in range(N):
board.append(list(map(int, input().split())))
max_sum = 0
# 1번 도형 확인
for i in range(N):
for j in range(M-3):
if board[i][j] + board[i][j+1] + board[i][j+2] + board[i][j+3] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i][j+2] + board[i][j+3]
# 1번 도형 회전 확인
for i in range(N-3):
for j in range(M):
if board[i][j] + board[i+1][j] + board[i+2][j] + board[i+3][j] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+2][j] + board[i+3][j]
# 2번 도형 확인
for i in range(N-1):
for j in range(M-1):
if board[i][j] + board[i][j+1] + board[i+1][j] + board[i+1][j+1] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i+1][j] + board[i+1][j+1]
# 3번 도형, 3번 도형 변형, 4번 도형, 5번 도형 변형 확인
for i in range(N-2):
for j in range(M-1):
# 3번 도형
if board[i][j] + board[i+1][j] + board[i+2][j] + board[i+2][j+1] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+2][j] + board[i+2][j+1]
# 3번 도형 180도 회전 도형
if board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+2][j+1] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+2][j+1]
# 3번 도형 오른쪽으로 270도 회전 도형
if board[i][j] + board[i+1][j] + board[i+2][j] + board[i][j+1] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+2][j] + board[i][j+1]
# 3번 도형 좌우 대칭 도형
if board[i][j+1] + board[i+1][j+1] + board[i+2][j+1] + board[i+2][j] > max_sum:
max_sum = board[i][j+1] + board[i+1][j+1] + board[i+2][j+1] + board[i+2][j]
# 4번 도형
if board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1]
# 4번 도형 상하 대칭 도형
if board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j] > max_sum:
max_sum = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j]
# 5번 도형 오른쪽으로 90도 회전 도형
if board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1] > max_sum:
max_sum = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1]
# 5번 도형 오른쪽으로 270도 회전 도형
if board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j]
# 3번 도형 변형, 4번 도형 변형, 5번 도형, 5번 도형 변형 확인
for i in range(N-1):
for j in range(M-2):
# 3번 도형 오른쪽으로 90도 회전 도형
if board[i][j] + board[i+1][j] + board[i][j+1] + board[i][j+2] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i][j+1] + board[i][j+2]
# 3번 도형 상하 대칭 도형
if board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] + board[i][j+2] > max_sum:
max_sum = board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] + board[i][j+2]
# 3번 도형 오른쪽으로 90도 회전 후 상하 대칭 도형
if board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2]
# 3번 도형 오른쪽으로 90도 회전 후 좌우 대칭 도형
if board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+2] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+2]
# 4번 도형 오른쪽으로 90도 회전 도형
if board[i][j+1] + board[i][j+2] + board[i+1][j] + board[i+1][j+1] > max_sum:
max_sum = board[i][j+1] + board[i][j+2] + board[i+1][j] + board[i+1][j+1]
# 4번 도형 오른쪽으로 90도 회전 후 좌우 대칭 도형
if board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+1][j+2] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+1][j+2]
# 5번 도형
if board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+1] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+1]
# 5번 도형 180도 회전 도형
if board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] > max_sum:
max_sum = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2]
print(max_sum)
티어 : Gold 5 시간 제한 : 2 초 메모리 제한 : 256 MB 알고리즘 분류 : 브루트포스 알고리즘
문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
예제 입출력
힌트
예제 1의 경우 5455++ 또는 5459--
Algorithm
완전 탐색 이용 1. 고장난 버튼을 제거하고 찾는 채널과 가장 가까운 수 만들기 2. 해당 숫자의 자리수 + (찾는 채널 - 만든 수) Return
고려해야 할 조건들이 너무 많아 힘들었던 문제 ㅠㅠ
Code
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
error_key = []
if M > 0:
error_key = list(map(int, input().split()))
# 사용 가능한 키는 True, 그렇지 않으면 False
error_keys = dict()
for i in range(10):
if i not in error_key:
error_keys[i] = True
else:
error_keys[i] = False
# 보고싶은 채널과 가장 가까운 숫자 만들기
one_step = 5000011
# 찾는 채널보다 작은 수로 가까운 숫자 만들기
for num in range(N, -1, -1):
# 찾는 채널이 100이거나 M이 0이거나 숫자가 모두 고장이면 break
if N == 100 or M == 0 or M == 10:
break
# keys 중 error_key에 없는 숫자를 이용해 해당 숫자 만들 수 있으면 break
temp = list(str(num))
# error_key가 아닌 key 개수 세기
count = 0
for i in temp:
if error_keys[int(i)]:
count += 1
# count가 temp의 길이와 같으면 만들 수 있는 숫자
if count == len(temp):
one_step = num
break
# 찾는 채널보다 큰 수로 가까운 숫자 만들기
num = N
while True:
# 찾는 채널이 100이거나 M이 0이거나 숫자가 모두 고장이면 break
if N == 100 or M == 0 or M == 10:
break
# keys 중 error_key에 없는 숫자를 이용해 해당 숫자 만들 수 있으면 break
temp = list(str(num))
# error_key가 아닌 key 개수 세기
count = 0
for i in temp:
if error_keys[int(i)]:
count += 1
# count가 temp의 길이와 같으면 만들 수 있는 숫자
if count == len(temp):
# 찾는 채널보다 작은 채널의 숫자 차이가 작으면 갱신
if one_step < N:
if N - one_step > num - N:
one_step = num
break
else:
one_step = num
break
if one_step < N and num - N >= N - one_step:
break
num += 1
answer = 0
if N != 100:
if M == 10 or one_step == 5000011:
if M == 0:
answer = min(max(100-N, N-100), len(str(N)))
else:
answer = max(N - 100, 100-N)
# 100에서 +와 -만을 이용해 움직인 횟수가 one_step과의 차이보다 작으면 갱신
elif max(100-N, N-100) < max(N-one_step, one_step-N) + len(str(N)):
if one_step == 5000011:
answer = min(max(100-N, N-100), len(str(N)))
else:
answer = max(100-N, N-100)
# 숫자 중 고장난 키가 하나도 없으면 채널 번호 길이만큼 출력
elif M == 0:
answer = len(str(N))
else:
answer = len(str(one_step))
answer += max(N - one_step, one_step - N)
print(str(answer))
티어 : Silver 5 시간 제한 : 2 초 메모리 제한 : 4 MB 알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론, 중국인의 나머지 정리
문제
준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.
지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)
우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.
예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.
E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.
출력
첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.
예제 입출력
Algorithm
1. 현재 시간 1 증가 2. e, s, m 1 증가 ☞ 각각 15, 28, 19를 넘으면 1로 초기화
Code
E, S, M = map(int, input().split())
e, s, m = 0, 0, 0
time = 0
while True:
time += 1
if e == 15:
e = 1
else:
e += 1
if s == 28:
s = 1
else:
s += 1
if m == 19:
m = 1
else:
m += 1
if e == E and s == S and m == M:
break
print(time)
티어 : Silver 3 시간 제한 : 1 초 메모리 제한 : 128 MB 알고리즘 분류 : 구현, 브루트포스 알고리즘
문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
예제 입출력
힌트
예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.
Algorithm
1. 사탕의 색상을 2차원 리스트 board에 저장 2. board를 하나씩 확인하면서 행에 같은 사탕이 몇 개인지 세기 2.1. 행: board[i][j]부터 board[i][j+1]까지 같은 색이면 count + 1 다른 색이면 count 1로 초기화하고 continue 2.2. 열: board[i][j]부터 board[i+1][j]까지 같은 색이면 count + 1 다른 색이면 count 1로 초기화하고 continue 3. board를 하나씩 확인하면서 열에 같은 사탕이 몇 개인지 세기 3.1. 행: board[i][j]부터 board[i][j+1]까지 같은 색이면 count + 1 다른 색이면 count 1로 초기화하고 continue 3.2. 열: board[i][j]부터 board[i+1][j]까지 같은 색이면 count + 1 다른 색이면 count 1로 초기화하고 continue
Code
import sys
input = sys.stdin.readline
N = int(input())
board = []
for _ in range(N):
board.append(list(input().rstrip()))
# 행을 기준으로 다른 색상 교환
max_count = 1
for i in range(N):
for j in range(N-1):
# 인접한 행의 색상이 다르면 교환
if board[i][j] != board[i][j+1]:
board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
# 교환했을 때 사탕의 최대 개수 체크
# 행 확인
for x in range(N):
count = 1
for y in range(N-1):
# 인접한 행의 색상이 같으면 count 증가
if board[x][y] == board[x][y+1]:
count += 1
else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
if max_count < count:
max_count = count
count = 1
continue
if max_count < count:
max_count = count
# 열 확인
for y in range(N):
count = 1
for x in range(N-1):
# 인접한 열의 색상이 같으면 count 증가
if board[x][y] == board[x+1][y]:
count += 1
else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
if max_count < count:
max_count = count
count = 1
continue
if max_count < count:
max_count = count
# 교환했던 칸 원위치
board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
# 열을 기준으로 다른 색상 교환
for j in range(N):
for i in range(N-1):
# 인접한 열의 색상이 다르면 교환
if board[i][j] != board[i+1][j]:
board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
# 교환했을 때 사탕의 최대 개수 체크
# 행 확인
for x in range(N):
count = 1
for y in range(N-1):
# 인접한 행의 색상이 같으면 count 증가
if board[x][y] == board[x][y+1]:
count += 1
else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
if max_count < count:
max_count = count
count = 1
continue
if max_count < count:
max_count = count
# 열 확인
for y in range(N):
count = 1
for x in range(N-1):
# 인접한 열의 색상이 같으면 count 증가
if board[x][y] == board[x+1][y]:
count += 1
else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
if max_count < count:
max_count = count
count = 1
continue
if max_count < count:
max_count = count
# 교환했던 칸 원위치
board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
print(max_count)
