2024. 10. 13. 18:52ㆍ카테고리 없음
https://www.acmicpc.net/problem/12100
문제 설명
판을 상하좌우로 움직일때 숫자가 합쳐지는데 최대 5번 움직였을때 합쳐진 숫자의 최대값을 구하는 문제이다.
문제를 풀기전 했던 생각
왼쪽으로 기울였을때 숫자를 합치기 위해 배열의 오른쪽부터 합쳐야하는지 왼쪽부터 합쳐야하는지 따져보았다.
오른쪽부터 합치는경우 나중에 결과가 달라지니 왼쪽부터 합쳐야할거같은데 여러 경우를 생각했다.
맨 왼쪽숫자를 두고 오른쪽으로 이동하며 같은 수를 찾는 방식을 가장 먼저생각했는데 그러면 나중에 수를 배치할때의 방법이
안떠올라 옳은 접근방식이 아니란걸 알았다. 여러 방법들을 생각하다 큐에 넣고 연산을 한 후 배열에 다시 넣는 방법이 이상적임을
깨달았다.
최대값을 찾을때마다 전체 보드판을 봐야하는데 그것대로 복잡할거같아 브루트포스로 문제에 접근했다.
겪은 문제
1. 한번 움직였을때 각 숫자는 1번만 합쳐질수있는데 이부분 고려하지 못해 틀렸다.
2 아래 코드에서 m은 깊은 복사를 잘했는데 마지막줄 board는 옅은복사로 m을 복사해 각 시행이 이루어질때마다 보드판이 초기화되지않았다.
def simulate(level):
global result
global board
if level == 5:
maxValue = findMax(board)
if maxValue > result:
result = maxValue
return
m = [ b[:] for b in board]
for d in direction:
move(d,board)
simulate(level+1)
board = [ mm[:] for mm in m]
3. 아래의 코드에서 처음에 return max(list(max(m for m in M))) 을 했다.
M = [[4,8,2,1,2], [6,6,2,1,2], [5,7,2,1,2]]
위의 코드는 있을때 첫번째 인덱스가 가장 큰 6이 나온다.
return max(list(max(m) for m in M)) 이렇게 하거나 아래의 코드를 적어야 8이 나옴을 깨달았다.
이 문제를 해결하는데 가장 많은 시간을 할애했는데 리스트 컨프리핸션을 잘못쓰는것의 위험성을 깨달을수있었다.
def findMax(M):
return max(map(max,M))
코드
""" 아이디어
1. 합치기
왼쪽으로 기울이는것을 생각하면 맨 왼쪽자리부터 합쳐진다.
왼쪽으로 기울일때 1행이 2 2 0 2 라고 가정하자.
이때 숫자들만 다 뽑는다.
2 2 2
그 후 1번째 자리와 2번째 자리가 일치하면 합친다.
합쳐지는 경우에는 그 다음 시행에도 1번째 자리와 2번째 자리가 일치하는지 확인한다.
2 4 4 같이 합쳐지지 않는 경우에는 인덱스를 한칸 옮겨 2번째 자리와 3번째 자리를
합친다.
숫자가 3개인 경우 2회 시행하면 모든 숫자가 합치는 과정을 겪으니 큐의 길이 - 1 번 시행한다.
시행이 끝난후 수의 개수 만큼 인덱스별로 배치한다.
2. 최대값 확인하기
4방향으로 5번 시행한다.
가지치기를 할 수 있는가?
한번 기울일때마다 최대 1번 합쳐질 수 있으니
5-N 번째 시행의 보드판의 최대값에 2^n 만큼 최대 값을 가질 수 있다.
하지만 매 시행마다 최대값을 확인하여 없어지는 경우의 수가 많지 않을거같고 최대값을
확인하는 비용이 꽤 커 그냥 모두 시행하는 방향을 목표로한다.
보드판 형태를 기억하는 방법도 이와 비슷해 모두 시행해보며 최대값을 기록하는 것이 중요할것같다.
"""
n = int(input())
board = [list(map(int,input().split(" "))) for _ in range(n)]
direction = ['U','D','L','R']
u = []
def export(r,direction,M):
global u
if direction == 'L':
for i in range(n):
if M[r][i] != 0:
u.append(M[r][i])
M[r][i] = 0
elif direction == 'R':
for i in range(n-1,-1,-1):
if M[r][i] != 0:
u.append(M[r][i])
M[r][i] = 0
elif direction == 'U':
for i in range(n):
if M[i][r] != 0:
u.append(M[i][r])
M[i][r] = 0
elif direction == 'D':
for i in range(n-1,-1,-1):
if M[i][r] != 0:
u.append(M[i][r])
M[i][r] = 0
def union():
if len(u) < 2:
return
s_index = 0
e_index = 1
count = len(u)-1
while True:
if count <= 0:
break
if u[s_index] == u[e_index]:
u.pop(s_index)
u[s_index] = u[s_index]*2
count += -1
s_index += 1
e_index += 1
count += -1
def send(r,direction,M):
global u
if direction == 'L':
l = len(u)
for i in range(l):
v = u.pop(0)
M[r][i] = v
elif direction == 'R':
l = len(u)
for i in range(l):
v = u.pop(0)
M[r][-(i+1)] = v
elif direction == 'U':
l = len(u)
for i in range(l):
v = u.pop(0)
M[i][r] = v
elif direction == 'D':
l = len(u)
for i in range(l):
v = u.pop(0)
M[-(i+1)][r] = v
def move(direction, M):
for i in range(n):
export(i,direction,M)
union()
send(i,direction,M)
def findMax(M):
return max(map(max,M))
result = 0
def simulate(level):
global result
global board
if level == 5:
maxValue = findMax(board)
if maxValue > result:
result = maxValue
return
m = [ b[:] for b in board]
for d in direction:
move(d,board)
simulate(level+1)
board = [ mm[:] for mm in m]
simulate(0)
print(result)
꽤나 빠르게 이쁜코드로 푼거같아 기분이 좋았다.