[BOJ] 12100 - 2048(Easy)
문제 링크
2048 (Easy)
킹받는 (Easy) ,,^^ 누구맘대로 이지야 ㅠ
문제 설명
다들 한번씩 플레이해봤을 2048게임과 같은 방식으로 동작하되 새로운 블록이 추가되지는 않는다.
N*N크기의 보드 위의 블록을 상하좌우로 이동시키는데 이때 같은 값을 가지는 블록 두개가 충돌 시 1개로 합쳐진다. 0은 빈칸을 나타내고, 나머지 값은 2이상 2048 이하인 2의 제곱꼴이다.
최대 5번을 이동시켜서 얻을 수 있는 최대값은?
문제 풀이
시도 1
처음에는 이런 식으로 접근했다. move()를 이용해서 dir방향으로 보드 위의 각 블록을 이동시키고, dfs를 이용해서 모든 경우의 수를 찾으려고 했다.
하지만 테스트 케이스를 돌려본 결과 생각하지 못했던 부분이
1. 이미 이번 회차에 합쳐진 블록은 다시 합칠 수 없음
문제 설명에도 나와있듯이,,^^
2. 아래로 혹은 오른쪽으로부터 합치는 경우 (0,0)~(N-1,N-1)의 순서로 순회하면 안됨
테스트케이스의 경우에, 왼쪽, 오른쪽으로 밀었을때 각각 저렇게 나와야 한다. 하지만 (0,0)부터 순회해서 이동시키는 경우에는 우측으로 밀었을때의 결과가 [[0,4,2],[0,8,4],[0,16,8]]과 같이 나온다.
아래로 혹은 오른쪽으로 합치는 경우에는 (N-1, N-1)부터 (0,0)까지의 순서로 이동시켜야 한다.
시도 2
import sys
import copy
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N = int(input())
answer = 0
board = []
for _ in range(N):
board.append(list(map(int, input().split())))
def in_bound(x, y):
if x in range(0,N) and y in range(0,N):
return True
else:
return False
def move(board, dir):
merged = [[0]*N for _ in range(N)]
if dir % 2 == 0:
start, end, inc = 0, N, 1
else:
start, end, inc = N-1, -1, -1
# 각각의 칸에 대해서
for i in range(start, end, inc):
for j in range(start, end, inc):
if board[i][j] != 0:
x, y = i, j
nx, ny = x + dx[dir], y + dy[dir]
while in_bound(nx, ny):
# 빈칸이면
if board[nx][ny] == 0:
board[nx][ny] = board[x][y]
board[x][y] = 0
x, y = nx, ny
nx, ny = x + dx[dir], y + dy[dir]
# 같은 숫자를 만나면
elif board[nx][ny] == board[x][y]:
if not merged[nx][ny]:
board[nx][ny] += board[x][y]
board[x][y] = 0
merged[nx][ny] = 1
break
# 다른 숫자를 만나면
else:
break
def dfs(board, count):
#print(count, board)
global answer
if count >= 5:
max_val = 0
for i in range(N):
max_val = max(max_val, max(board[i]))
answer = max(answer, max_val)
return
for i in range(4):
new_board = copy.deepcopy(board)
move(new_board, i)
#이동 가능하면
if new_board != board:
dfs(new_board, count+1)
#더 이상 이동이 불가능하면 -> 최대값 갱신
else:
max_val = 0
for j in range(N):
max_val = max(max_val, max(board[j]))
answer = max(answer, max_val)
dfs(board, 0)
print(answer)
느낀점
쉽지 않았넵 ,, 그래도 이번엔 다른거 참고 안하고 풀었다 ,,^__^ 다른 사람들은 어떻게 풀었는지 찾아봤는데 비슷한 로직으로 푼거 같다 ,,
코드 짜기 전에 수도코드를 좀 더 진득하게 생각하고 자세히 써본 다음에 푸는 습관을 들여야 겠다,, 그리고 문제도 똑바로 읽긔
Author And Source
이 문제에 관하여([BOJ] 12100 - 2048(Easy)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@woo0_hooo/BOJ-12100-2048Easy저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)