import sys
from collections import deque
def input():
return sys.stdin.readline().rstrip()
A = list(input())
B = list(input())
N = len(A)
A.sort()
B.sort()
A = deque(A[:(N+1)//2])
B = deque(B[N-N//2:N])
answer = ['?']*N
left = 0
right = N-1
for idx in range(N):
if idx%2:
if A and A[0] >= B[-1]:
answer[right] = B.popleft()
right -= 1
else:
answer[left] = B.pop()
left += 1
else:
if B and B[-1] <= A[0]:
answer[right] = A.pop()
right -= 1
else:
answer[left] = A.popleft()
left += 1
print(''.join(answer))
문제를 보면, 구사과는 가장 사전순으로 빠르게,
큐브러버는 사전순으로 느리게이다.
이때 그냥 생각해보면 정렬하고,
앞에서부터, 구사과는 작은걸
큐브러버는 큰걸 둔다고 생각을 하고 두면, 안된다.
이 문제는 최적의 방법이므로, 두사람의 패를 알고 있다고 가정을 하고 풀어야한다.
만약 구사과가 가진 문자열 중 가장 작은 것이, 큐브러버의 문자열중 가장 큰것보다, 작을때에는
작은걸 제일 앞에 두면 된다.
하지만 가장 작은것이 큐브러버 문자열 중 가장 큰것보다 크거나 같을때에는,
자신이 무조건 써야하는 패중에서 가장 큰걸 가장 뒤에 두는게 사전순으로 빠르게 하는방법이다.
이와 같이
큐브러버도 자신이 가진 문자열 중 가장 큰 것이, 구사과가 가진 가장 작은 문자열보다 클때에는
import sys
def input():
return sys.stdin.readline().rstrip()
N,W = map(int,input().split())
dp = [[0 for _ in range(W+1)] for _ in range(N)]
first = int(input())
if first == 1:
dp[0][0] = 1
else:
dp[0][1] = 1
for ind in range(1,N):
num = int(input())
num -= 1
dp[ind][0] = dp[ind-1][0]
if not num:
dp[ind][0] += 1
for j in range(1,W+1):
dp[ind][j] = max(dp[ind-1][j],dp[ind-1][j-1])
if j%2 == num:
dp[ind][j] += 1
print(max(dp[N-1]))
다이나믹 프로그래밍을 이용한 문제였다.
2차원 배열 dp을 정의했다.
dp[N][W] 는 n번째일때의 w 번 이동했을때의 최대값인 경우로 dp 배열을 정의했다.
그러면 dp[n][w]일때의 값은 dp[n-1][w-1] 이나 dp[n-1][w]의 최대값이 될것이다. 이동을 했거나, 이동을 하지 않았거나 이다.
그리고 짝수번을 움직였을때에는 무조건 1번 나무에 있고, 홀수번을 움직였을때에는 무조건 2번나무에 위치해있는다.
이점을 이용해
dp[n][w] = max(dp[n-1][w-1],dp[n-1][w])을 비교해주고,
현재 떨어진 과일나무의 위치와 움직인 횟수의 홀수짝수가 동일 할 때에는
해당 위치에서 현재 떨어지는 열매를 먹을수 있는것이므로, 1개씩 더해주면 된다.
dp배열을 정의하고, 움직인 횟수가 홀수 짝수일때를 비교를 해, 1번나무에 위치해있는지,
2번나무에 위치해있는지를 구분해주면, 3차원 배열을 쓰지 않고도, 2차원 배열만으로도 풀수 있는 문제였따.
import sys
def input():
return sys.stdin.readline().rstrip()
def check(arr):
if max(arr) - min(arr) <=K:
return False
return True
def push():
min_value = min(arr[-1])
for i in range(N):
if arr[-1][i] == min_value:
arr[-1][i] += 1
def roll(arr):
row,col = 1,1
new_N = N
time = 0
while True:
new_temp = [[-1 for _ in range(new_N-col)] for _ in range(row+1)]
for y in range(col,new_N):
new_temp[-1][y-col] = arr[-1][y]
for y in range(col):
for x in range(len(arr)):
new_temp[y][len(arr)-x-1] = arr[x][y]
new_N = new_N-col
if time%2:
row += 1
col += 1
time += 1
arr = [row[:] for row in new_temp]
row_N = len(new_temp)
if row_N*(col+1) >N:
break
return arr
def outOfbound(x,y,row,col):
if 0<=x<row and 0<=y<col:
return False
return True
def blow():
row = len(new_arr)
col = len(new_arr[0])
temp = [[0 for _ in range(col)] for _ in range(row)]
for x in range(row):
for y in range(col):
if new_arr[x][y] == -1:continue
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if outOfbound(nx,ny,row,col):continue
if new_arr[nx][ny] == -1:continue
if new_arr[x][y] - new_arr[nx][ny] >=5:
gap = (new_arr[x][y] - new_arr[nx][ny])//5
temp[x][y] -= gap
temp[nx][ny] += gap
for x in range(row):
for y in range(col):
new_arr[x][y] += temp[x][y]
def flatting(maze):
temp_arr = [[]]
row = len(maze)
col = len(maze[0])
for y in range(col):
for x in range(row-1,-1,-1):
if maze[x][y]==-1:continue
temp_arr[-1].append(maze[x][y])
return temp_arr
def spread():
spread_arr = flatting(new_arr)
temp = [[-1 for _ in range(N//4)] for _ in range(4)]
for x in range(4):
if x%2:
start_x = N//4*x
y = 0
while y<N//4:
temp[x][y] = spread_arr[-1][start_x+y]
y += 1
else:
y = N//4-1
if x == 2:
start_x = 0
else:
start_x = N//4*2
while y>=0:
temp[x][y] = spread_arr[-1][start_x]
start_x += 1
y -= 1
return temp
N,K = map(int,input().split())
arr = [list(map(int,input().split()))]
dx = [-1,0,1,0]
dy = [0,-1,0,1]
turn = 0
while check(arr[-1]):
push()
new_arr = roll(arr)
blow()
new_arr = spread()
blow()
arr = flatting(new_arr)
turn += 1
print(turn)
