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))
문제를 보면, 구사과는 가장 사전순으로 빠르게,
큐브러버는 사전순으로 느리게이다.
이때 그냥 생각해보면 정렬하고,
앞에서부터, 구사과는 작은걸
큐브러버는 큰걸 둔다고 생각을 하고 두면, 안된다.
이 문제는 최적의 방법이므로, 두사람의 패를 알고 있다고 가정을 하고 풀어야한다.
만약 구사과가 가진 문자열 중 가장 작은 것이, 큐브러버의 문자열중 가장 큰것보다, 작을때에는
작은걸 제일 앞에 두면 된다.
하지만 가장 작은것이 큐브러버 문자열 중 가장 큰것보다 크거나 같을때에는,
자신이 무조건 써야하는 패중에서 가장 큰걸 가장 뒤에 두는게 사전순으로 빠르게 하는방법이다.
이와 같이
큐브러버도 자신이 가진 문자열 중 가장 큰 것이, 구사과가 가진 가장 작은 문자열보다 클때에는
def solution(board, skill):
answer = 0
N = len(board)
M = len(board[0])
skill_board = [[0 for i in range(M+2)] for _ in range(N+2)]
cnt = 0
for sk in skill:
sk_type, r1,c1,r2,c2 ,degree = sk
if sk_type == 1:
degree = -degree
r1 +=1; r2+=1; c1+=1; c2+=1
skill_board[r1][c1] += degree
skill_board[r1][c2+1] -= degree
skill_board[r2+1][c1] -= degree
skill_board[r2+1][c2+1] += degree
for x in range(1,N+1):
for y in range(1,M+1):
skill_board[x][y] = skill_board[x][y] + skill_board[x-1][y] + skill_board[x][y-1] - skill_board[x-1][y-1]
for x in range(N):
for y in range(M):
if board[x][y] +skill_board[x+1][y+1] >0:
answer += 1
return answer
이 문제도 실전에서 풀지 못했던 문제였다.
7번 문제에 너무 힘을 쏟은 나머지, 마지막 20분동안 풀다가 범위 측정을 제대로 못해서, 풀지 못한 문제였다.
평소 2차원 누적합을 잘 다루지 않다보니, 범위를 구하는데 실수를 했고, 그 범위의 누적합을 구하는데 연산을 실후 했다.
이 문제에서 중요한 것은 폭발 범위에 맞춰서 누적합을 할 수 있게, 숫자들을 정리해 놓고, 누적합을 구하면 되는 문제이다.
폭발이 시작하는 r1,c1에는 +degree을 해주고,
폭발이 끝나는 위치인 r2+1,c1 , r1,c2+1에는 -degree을 해준다.
그리고 중요한 것은 r2+1, c2+1 에서는 +degree를 해주는 것이다.
이 누적합을 마킹해놓은 상태에서 가로로 1번 누적합 세로로 1번 누적합을 진행을 한다고 생각을 해보면, 왜 그 위치에서 마킹을 해줘야하는지 이해할 수 있다.
이 문제는 누적합이라는 접근까지 했지만, 디버깅 할 시간이 부족해 풀지 못했던 아쉬웠던 문제였다..
dx = [-1,0,1,0]
dy = [0,1,0,-1]
N,M =0,0
def B_turn(curboard,A,B,turn):
x,y = B
if curboard[x][y] == 0:
return (-1,turn)
flag = False
winner = []
loser = []
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<N and 0<=ny<M:
if curboard[nx][ny] == 1:
new_board = [row[:] for row in curboard]
new_board[x][y] = 0
iswin,new_turn = A_turn(new_board,A,(nx,ny),turn+1)
if iswin == -1:
winner.append(new_turn)
else:
loser.append(new_turn)
flag = True
if flag:
if winner:
return (1,min(winner))
else:
return (-1,max(loser))
else:
return (-1,turn)
def A_turn(curboard,A,B,turn):
x,y = A
if curboard[x][y] == 0:
return (-1,turn)
flag = False
winner = []
loser = []
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<N and 0<=ny<M:
if curboard[nx][ny] == 1:
new_board = [row[:] for row in curboard]
new_board[x][y] = 0
iswin,new_turn = B_turn(new_board,(nx,ny),B,turn+1)
if iswin == -1:
winner.append(new_turn)
else:
loser.append(new_turn)
flag = True
if flag:
if winner:
return (1,min(winner))
else:
return (-1,max(loser))
else:
return (-1,turn)
def solution(board, aloc, bloc):
global N,M
N = len(board)
M = len(board[0])
return A_turn(board,aloc,bloc,0)[1]
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차원 배열만으로도 풀수 있는 문제였따.
