T,N,D,K = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
tea_cnt = [0]*N
for ind in range(N):
left = ind
right = N-1
tea_time = arr[ind]
while left <=right:
mid = (left+right)//2
if arr[mid] >= tea_time+D:
right = mid -1
else:
left = mid + 1
tea_cnt[ind] = left - ind
dp = [[0]*(K+1) for _ in range(N+1)]
for idx in range(N):
for drink_coffee in range(1,K+1):
dp[tea_cnt[idx]+idx][drink_coffee] = max(dp[tea_cnt[idx]+idx][drink_coffee], dp[idx][drink_coffee-1]+tea_cnt[idx])
dp[idx+1][drink_coffee] = max(dp[idx+1][drink_coffee],dp[idx][drink_coffee])
for row in dp:
print(row)
print(max(map(max,dp)))
import sys
sys.setrecursionlimit(100000)
def dfs(node):
if visited[node]:
return
visited[node] = True
child_nodes = []
for next_node in graph[node]:
if not visited[next_node]:
child_nodes.append(next_node)
if not len(child_nodes):
dp[node][0] = town_person[node]
return
for child_node in child_nodes:
dfs(child_node)
dp[node][0] += dp[child_node][1]
dp[node][1] += max(dp[child_node][0],dp[child_node][1])
dp[node][0] += town_person[node]
N = int(input())
town_person = [0] +list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
x,y = map(int,input().split())
graph[x].append(y)
graph[y].append(x)
visited = [False]*(N+1)
dp = [[0]*2 for _ in range(N+1)]
# 0번 인덱스 : 참여를 했을때
# 1번 인덱스 : 참여를 안 했을때
dfs(1)
print(max(dp[1]))
def solution(ind,diff):
if diff > 250000:
return -INF
if ind == N:
if diff == 0:
return 0
else:
return -INF
if dp[ind][diff] != -1:
return dp[ind][diff]
dp[ind][diff] = solution(ind+1,diff+arr[ind])
dp[ind][diff] = max(dp[ind][diff],solution(ind+1,diff))
if arr[ind] > diff:
dp[ind][diff] = max(dp[ind][diff],diff + solution(ind+1,arr[ind]-diff))
else:
dp[ind][diff] = max(dp[ind][diff],arr[ind] + solution(ind+1,diff-arr[ind]))
return dp[ind][diff]
N = int(input())
arr = list(map(int,input().split()))
arr = arr + [0]
INF = float('inf')
dp = [[-1] * 500001 for _ in range(N+1)]
result = solution(0,0)
if result == 0:
print(-1)
else:
print(result)
힘들게 풀었던 문제이다.
dp의 테이블에서 행은 현재의 index를 말하며, 열은 두 탑의 격차의 절대값을 말한다.
재귀함수를 통해 짰는데.
첫번째 : 해당 블록을 높이가 더 높은 쪽에 놓았을때,
두번째 : 해당 블록을 놓지 않았을때
세번째 : 높이가 낮은 블록에 놓았을 때 : 이 때 주의해야할 것은 현재 공통적으로 쌓아올려진 높이는 diff와 arr[ind]의 두 크기 중 작은 것에 된다.
이렇게 3가지 경우로 나뉘며, 세번째에는 격차가 클때와 현재 블록이 클때로 나뉘어서 된다.
이렇게 재귀를 하면서 마지막에서 들어온 diff가 0이면 높이가 같은것이므로 0을 반환해주고, 그게 아니면 두 높이가 다른것이므로, -INF를 반환해준다.
이게 내 첫번째 풀이였고, 실행시간은 3900ms로 엄청 느렸다.
그래서 다른 사람 풀이를 보고 공부한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int,input().split()))
if N == 1:
print(-1)
else:
total_sum = sum(arr)
dp = [[-1] * total_sum for _ in range(N)]
dp[0][0] = 0
dp[0][arr[0]] = arr[0]
for ind in range(N-1):
for j in range(total_sum//2+1):
if dp[ind][j] != -1:
# 다음 거의 블록을 쓰지 않을때
dp[ind+1][j] = max(dp[ind][j],dp[ind+1][j])
# 두 탑 중 더 높은 탑쪽에 블록을 쌓을때
if j + arr[ind+1] < total_sum:
dp[ind+1][j+arr[ind+1]] = max(dp[ind+1][j+arr[ind+1]],dp[ind][j]+arr[ind+1])
# 더 낮은 탑 쪽에 쌓는데 새로 쌓는 블록이 기존 블록보다 높을때 와 아닐때
if arr[ind+1] > j:
dp[ind+1][arr[ind+1]-j] = max(dp[ind+1][arr[ind+1]-j],dp[ind][j] + arr[ind+1]-j)
else:
dp[ind+1][j-arr[ind+1]] = max(dp[ind+1][j-arr[ind+1]],dp[ind][j])
if dp[-1][0] == 0:
print(-1)
else:
print(dp[-1][0])
위와 dp 테이블은 동일하다. 그런데 전체 input의 합을 구하고, 그거의 반만큼만 반복을 돌리도록 했다.
그래서 위에서는 재귀를 통해서 돌아가다 보니, 무조건 3개의 함수가 실행되다보니 밑의 코드보다 훨씬 오래걸린다.
밑의 코드는 50*250000이 최대 횟수로 볼수 있으므로, 위의 것보다 연산량에 이득을 본것 같다.
여기도 위와 비슷하게,
아무것도 놓지 않았을때
두 탑 중 더 높은 탑쪽에 쌓았을때,
두 탑 중 더 낮은 탑쪽에 쌓았을때,
를 구분해서 놓으면 된다.
그리고 dp에 저장되는 값은 해당 index에서 두 탑의 높이가 diff만큼 차이가 날때, 그때 더 높은탑의 크기를 저장해놓는 것이므로,
import sys
input = sys.stdin.readline
T = int(input())
def divide_two(ind_X,ind_Y):
if ind_X == ind_Y:
return books[ind_X]
cache_data = dp[ind_X][ind_Y]
if cache_data != -1:
return cache_data
temp = float('inf')
mid_sum = prefix_sum[ind_Y+1] - prefix_sum[ind_X]
for k in range(ind_X,ind_Y):
temp = min(temp,divide_two(ind_X,k)+divide_two(k+1,ind_Y)+mid_sum)
dp[ind_X][ind_Y] = temp
return temp
for _ in range(T):
N = int(input())
dp = [[-1]*N for _ in range(N)]
books = list(map(int,input().split()))
prefix_sum = [0]*(N+1)
for i in range(1,N+1):
prefix_sum[i] = prefix_sum[i-1] + books[i-1]
result = float('inf')
for i in range(N-1):
result = min(result,divide_two(0,i)+divide_two(i+1,N-1))
print(result)
어렵게 푼 문제이다.
먼저 특정 범위의 합을 구해야하기 때문에, prefix_sum을 먼저 구해준다.
그리고 재귀를 통해, 특정 위치로 나누었을때의 최소값을 구하는 함수를 통해 구해준다.
만약 0~N-1 칸이 있다고 했을때, 0~i 와 i+1~N-1을 나눠서 소분해서 구해주면 된다.
전체 0~N-1칸을 생각해보지 말고,
작은 공간 A ~ A+2 칸이 있다고 해보자,
A | | A+1 | | A+2
30 | | 40 | | 50
라고 하면
1번 경우 : 30 // 40 + 50
2번 경우 : 30 + 40 // 50
각각을 구해보면
1번 경우 : 90 + 90 + 30 = 90 + 120 = 210
2번 경우 : 70 + 70 + 50 = 70 + 120 = 190
그러면 A~A+2칸에서 가장 적게 구하는 것은 30+40 // 50 일때이다.
그리고 위의 경우를 봐보면 120은 30 + 40 + 50을 다 더한거와 같고, 그 앞의 값만 바뀐다는 것을 알 수 있다.
결국 정리하면 divide_two라는 함수에 들어왔을때 ind_X 와 ind_Y가 같으면 books[ind_X]의 값을 반환해주면 되고,
그 외의 경우에는 ind_X와 ind_Y의 사이값으로 나뉘었을때를 가정하고, 재귀를 통해 최소값을 구해주면 된다.
또한 이렇게 구한 값들은 변하지 않기 때문에
dp에 저장을 해주면 된다. dp[ind_X][ind_Y] 는 ind_X에서 ind_Y 까지의 범위를 계싼했을때 최저 값인 것이다.
위와 같이 구하면 파일 합치기의 최소값을 구할 수 있다.
하지만 이 방법은 N^3을 돌기 때문에 시간이 오래걸린다.
그래서 다른 사람들의 풀이를 보고 찾은 방법은 다음과 같다.
# # Knuth's Optimization
# # https://wogud6792.tistory.com/20
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N = int(input())
books = list(map(int,input().split()))
prefix_sum = [0]*(N+1)
INF = float('inf')
dp =[[INF] *N for _ in range(N)]
min_k_store_array = [[0]*N for _ in range(N)]
for i in range(N):
dp[i][i] = 0
min_k_store_array[i][i] = i
prefix_sum[i+1] = prefix_sum[i] + books[i]
for term in range(1,N):
for i in range(N-term):
j = term+i
for k in range(min_k_store_array[i][j-1],min_k_store_array[i+1][j]+1):
if k<N-1 and dp[i][j] > dp[i][k]+dp[k+1][j]+ prefix_sum[j+1] - prefix_sum[i]:
dp[i][j] = dp[i][k]+dp[k+1][j] + prefix_sum[j+1] - prefix_sum[i]
min_k_store_array[i][j] = k
print(dp[0][N-1])
from itertools import permutations
from collections import deque
def outOfrange(x,y):
if 0 > x or x >3 or y<0 or y>3:
return True
return False
def dfs(start,end,copy_board):
dp = [[-1]*4 for _ in range(4)]
dp[start[0]][start[1]] = 0
stack = deque()
stack.append((start[0],start[1]))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while stack:
x,y = stack.popleft()
for i in range(4):
repeat = 0
while True:
nx = x + dx[i]*repeat
ny = y + dy[i]*repeat
if outOfrange(nx+dx[i],ny+dy[i]) or (repeat!=0 and copy_board[nx][ny]):
break
repeat += 1
for re in (1,repeat):
nx = x + dx[i] * re
ny = y + dy[i] * re
if outOfrange(nx,ny):
continue
if dp[nx][ny] == -1:
dp[nx][ny] = dp[x][y] + 1
stack.append((nx,ny))
if dp[end[0]][end[1]] != -1:
return dp[end[0]][end[1]]
return dp[end[0]][end[1]]
def find_command(x,y,find_card,copy_board):
dis1 = dfs((x,y),find_card[0],copy_board)
dis2 = dfs(find_card[0],find_card[1],copy_board)
return dis1+dis2
def solution(board, r, c):
answer = float('inf')
card_list = [[] for _ in range(7)]
card_numbers = set()
for x in range(4):
for y in range(4):
if board[x][y]:
card_list[board[x][y]].append((x,y))
card_numbers.add(board[x][y])
card_cnt = len(card_numbers)
for combi in permutations(card_numbers):
predict_dict = {}
for k in range(1<<card_cnt):
distance = 0
mouse_cursor_x = r
mouse_cursor_y = c
copy_board = [row[:] for row in board]
temp = ''
for ind,num in enumerate(combi):
start = int(bool((k&1<<(ind))))
end = (start+1)%2
temp += str(start)
find_card = [card_list[num][start],card_list[num][end]]
if not predict_dict.get(temp):
distance += find_command(mouse_cursor_x,mouse_cursor_y,find_card,copy_board)
predict_dict[temp] = distance
else:
distance = predict_dict[temp]
mouse_cursor_x = card_list[num][end][0]
mouse_cursor_y = card_list[num][end][1]
copy_board[card_list[num][start][0]][card_list[num][start][1]] = 0
copy_board[card_list[num][end][0]][card_list[num][end][1]] = 0
if distance > answer:
break
if answer > distance:
answer = distance
return answer+2*card_cnt
a = solution([[1,0,2,0],[6,2,4,0],[0,0,1,0],[6,0,0,4]],1,0)
print(a)
문제 자체는 BFS+순열+조합으로 간단해보였지만, 구현하는데 난이도가 컸던 문제였다.
기본 풀이 자체는 다음과 같다.
카드번호 1,2,3이 있다고 하면
1,2,3을 순열로 먼저 없앨 카드별 순서를 정해준다.
그리고 각 카드는 2장씩 있으므로, A,B 가 있다고 치면
1A->1B
1B->1A는 다를 것이다.
이 모든 경우를 돌려서 결과를 얻는 것이다.
그래서 먼저 나는 card_numbers에 이 보드에 있는 카드번호들을 저장해두고 permutations 모듈을 사용해서 순열을 만들었다 그리고 난뒤, 카드의 앞뒷면을 정해주기 위해 조합을 만들었다.
만약 우리가 카드가 3장이 있다고 하면 이 카드의 앞뒷면을 만들수 있는 가짓수는
000
001
010
011
100
101
110
111
이런식으로 총 8가지가 있을수 있다. 위의 가지수를 각비트로 봐보면 0~7까지인걸 알수 있다. 그러므로 저는 카드의 개수가 N이라고 하면, 2**N 만큼 range를 돌리고, 각 permutations으로 나오는 각각의 카드 index와 비트연산을 해서, 해당 카드의 앞뒷면의 순서를 결정해주었다.
이렇게 한뒤 현재 커서위치 -> 먼저 찾을 카드위치 -> 나중 찾을 카드위치 순으로, bfs를 돌렸다.
bfs를 돌릴때, ctrl 이동과 일반적인 한칸이동을 동시에 시행했다. 범위 밖을 나가던지, 아니면 카드가 있는 위치이던지, 그 위치까지의 길이를 기억해놓은뒤, 그 만큼을 dp라는 visited를 담당하는 행렬에 저장을해주었다. 그리고 우리가 찾는 목적지에 도착하면, return 해주는 방식으로 했다.
이렇게 bfs를 전부 돌린뒤에는 copy한 board에서 우리가 현재 뒤집은 카드들의 정보를 0으로 바꿔주고, 마우스 커서위치는 마지막 카드위치로 바꿔주는 작업을 해준다.
위 풀이 방식은 아슬아슬하게 시간을 통과한지라 여러부분에서 시간을 줄여주었다. 위에서 했듯이 bfs에서 매번 도착지점을 판별해주는 것이 첫번째 방법이었고, distance가 저장된 answer 보다 커지면 탐색을 중단해주는것도 그 방안이었다.
이렇게 구한 answer에 현재 카드의 종류의 2배만큼 더해서 출력해주면된다.
from collections import deque
import functools
def solution(board,r,c):
card_dict = [[] for i in range(7)]
card_tuple = set()
for x in range(4):
for y in range(4):
if board[x][y]:
card_dict[board[x][y]].append((x,y))
card_tuple.add(board[x][y])
card_tuple = tuple(card_tuple)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def outOfrange(x,y):
if 0 > x or x >3 or y<0 or y>3:
return True
return False
@functools.lru_cache(maxsize=None)
def bfs(s,t,cards):
if s == t:
return 0
stack = deque()
stack.append((s[0],s[1],0))
visited = set()
while stack:
x,y,cnt = stack.popleft()
for i in range(4):
repeat = 0
while True:
nx = x + dx[i]*repeat
ny = y + dy[i]*repeat
if outOfrange(nx+dx[i],ny+dy[i]) or (repeat != 0 and board[nx][ny] in cards):
break
repeat += 1
for re in [1,repeat]:
nx = x + dx[i]*re
ny = y + dy[i]*re
if outOfrange(nx,ny):
continue
if (nx,ny) == t:
return cnt + 1
if (nx,ny) not in visited:
visited.add((nx,ny))
stack.append((nx,ny,cnt+1))
@functools.lru_cache(maxsize=None)
def find_card_short_count(cur_position,cards):
if len(cards) == 0:
return 0
min_distance = float('inf')
for pick_card in cards:
position1,position2 = card_dict[pick_card]
remain_cards = tuple(card for card in cards if card != pick_card)
direction1 = bfs(cur_position,position1,cards) + bfs(position1,position2,cards) + find_card_short_count(position2,remain_cards)
direction2 = bfs(cur_position,position2,cards) + bfs(position2,position1,cards) + find_card_short_count(position1,remain_cards)
min_distance = min(min_distance,direction1,direction2)
return min_distance
answer = len(card_tuple)*2 + find_card_short_count((r,c),card_tuple)
return answer
a = solution([[1, 0, 0, 3], [2, 0, 0, 0], [0, 0, 0, 2], [3, 0, 1, 0]], 1, 0)
print(a)
기본적인 풀이는 비슷하다. 대신 이 풀이는 위에서 복잡하게 비트연산을 통해 결정하는 것이 아닌, 재귀함수를 통해, 순열과 조합을 구현했고, functools.lru_cache를 통해 메모라이즈를 해주었다.
이 두 방식을 통해 시간이 획기적으로 줄어들었다.
이 풀이는 크게 2가지의 함수로 나뉠수 있다. find_card_short_count라는 함수와 bfs 함수이다.
bfs는 A->B까지 가는 최소 명령어를 찾아주는 것이다. 여기서 카드의 위치를 판단하는것은 cards라는 tuple을 통해, 있는지 판별을 해준다.
여기서 중요한것은 find_card_short_count라는 함수이다. 이 함수의 역할은 재귀를 통해 순열을 만드는 것이다.
cur_position은 현재 커서의 위치이고, cards는 현재 남아있는 카드들의 번호들이다.
이 cards를 반복문을 돌리면서 그 카드를 제거할 카드라 생각하고, cards에서 현재 선택한 card를 제외한 나머지 카드들을 remain_cards로 남겨준다.
위에서 설명했던 것처럼 한 카드에서도 먼저 제거할 카드를 선택을 해야한다. 그 방법으로 direction1과 direction2로 나뉘어서 해주었다.
한 카드에서 position1 과 position2가 있다고 하면 제거할 수 있는 방법은 두가지이다.
현재 커서위치 -> position1까지의 거리를 구해주고 position1 -> position2 까지의 거리를 구해준다. 그러면 마지막 커서의 위치는 position2가 되고 position2와 remain_cards를 가지고 find_card_short_count를 해주면 된다.
이런 방식으로 현재 커서 위치 -> position2 -> position1도 똑같이 해준다.
def dfs(x,y):
global N,M
if x == N-1 and y == M-1:
return 1
if dp[x][y] != -1:
return dp[x][y]
else:
dp[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<N and 0<=ny<M:
if arr[nx][ny] < arr[x][y]:
dp[x][y] += dfs(nx,ny)
return dp[x][y]
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*M for _ in range(N)]
print(dfs(0,0))
DP 와 DFS가 결합된 문제였다. 최소로 도달한거리를 DP에 저장해서 얻는것이었다. 마지막 우리가 도달해야하는 위치만 초기값을 1로 주고, 나머지는 전부 0으로 초기화한뒤 역으로 계싼해서 오는것이다.
def dfs(W,H):
if W == 0:
return 1
if dp[W][H]:
return dp[W][H]
dp[W][H] = dfs(W-1,H+1)
if H>0:
dp[W][H] += dfs(W,H-1)
return dp[W][H]
while True:
N = int(input())
if not N:
break
dp = [[0]*31 for _ in range(N+1)]
print(dfs(N,0))
재귀적으로 푸는 방식이다.
한알로 먹는 먹을수 있는 개수를 W, 반알로 먹을 수 있는 개수를 H로 두고 재귀적으로 풀면 된다.
원래 들어온 W,H에서 기본적으로 W가 남아있으면, 한알을 꺼내먹을수 있기에 W-1,H+1로 함수를 실행시켜준다.
그리고 만약 H가 있다면, 반알을 먹을수도 있으므로, W,H-1로 함수를 실행시켜준다.
그러다가 한알짜리 알약이 전부 떨어지면, 남은경우는 반알을 전부 먹는것이므로 return 1을 해주며, 중단해준다.
이렇게 해서 전체 날짜에서 먹을수 있는 날짜를 구하면 된다.
dp = 31*[0]
dp[1] = 1
dp[0] = 1
for n in range(2,31):
for i in range(n):
dp[n] += dp[i]*dp[n-i-1]
while True:
N = int(input())
if not N:
break
print(dp[N])
위와 같은 형태의 문제를 카탈란 수라고 한다. 자세한 설명은 아래의 사이트에서 읽어보면 된다.
