a= int(input())
def cal(a):
temp = []
for i in a:
temp.append(i-1)
if i%3==0:
temp.append(i/3)
if i%2==0:
temp.append(i/2)
return temp
cnt=0
minimum=[a]
while True:
if a==1:
print(cnt)
break
temp=minimum[:]
minimum=[]
minimum=cal(temp)
cnt+=1
if min(minimum)==1:
print(cnt)
break
유명한 DP 문제이다.
각각의 연산을 한뒤에 새롭게 옮겨가는 LIST를 따로 만들어주고, 그걸 갱신하면서 횟수가 어느회차인지 알면된다.
N = int(input())
number_list = [N]
cnt = 0
flag = False
if N == 1:
print(0)
else:
while True:
new_number = []
for numbers in number_list:
if numbers == 1:
flag = True
break
if not numbers%3:
new_number.append(numbers/3)
if not numbers%2:
new_number.append(numbers/2)
new_number.append(numbers-1)
if flag:
print(cnt)
break
cnt += 1
number_list = new_number[:]
N = int(input())
arr = list(map(int,input().split()))
minus_inf = -float('inf')
dp = [[minus_inf]*N for _ in range(2)]
dp[0][0] = arr[0]
for ind in range(1,N):
dp[0][ind] = max(dp[0][ind-1]+arr[ind],arr[ind])
dp[1][ind] = max(dp[0][ind-1],dp[1][ind-1]+arr[ind])
print(max(map(max,dp)))
DP 관련 문제이다. 점화식을 찾고, 그걸 표현하는데 오래걸렸다.
기본 문제풀이 원리는 다음과 같다. 2개의 DP를 만들어
한쪽은 원래 그대로의 수열을 표현했을 때, 최대값을 저장해놓은 DP 배열
다른 한쪽은 수열 중 한 부분을 뺐을때, 최대값을 저장해놓는 DP 배열이다.
DP[flag][IDX] = flag가 0이면 계속해서 연속인 배열, 1이면, 배열 중 한 인덱스를 뺏을때의 배열을 나타낸다.
idx는 현재의 위치를 나타낸다.
먼저 원래 그대로 배열을 표현했을때 최대값이 될수 있는것은
현재 위치를 IDX라고 할시, DP[0][IDX] +arr[IDX]이나, arr[IDX] 중에 최대값이다. 계속 연속되는 합 같은경우 계속 이어져 오거나 현재위치부터 다시 시작하거나 둘중 하나이기 때문에 둘중 큰 값을 DP에 저장해놓는다.
그리고 배열 중 한 부분을 뺐을때 최대값이 될 수 있는것은
현재 IDX를 뺐을때와 현재 IDX는 포함하고 이전의 IDX 중 하나가 빠졌을때 둘 중 하나이다.
그러므로 점화식으로 나타내면 DP[1][IDX-1] + arr[IDX] , DP[0][IDX-1] 이다.
def solution(A,B):
result = [[0]*(len(B)+1) for _ in range(len(A)+1)]
for i in range(1,len(A)+1):
for j in range(1,len(B)+1):
if A[i-1] == B[j-1]:
result[i][j] = result[i-1][j-1] + 1
return max(map(max,result))
A = input()
B = input()
print(solution(A,B))
LCS 문제이다. 근데 이전에 풀었던 LCS와 다른 문제였다.
기본적인 틀은 똑같다. 대신 이 문제는 연속된 문자열이어야 하기 때문에, A[i-1] != B[i-1]일때는 아무것도 해주지 않는다.
N = int(input())
arr = list(map(int,input().split()))
dp = [[0]*21 for _ in range(N)]
dp[0][arr[0]] = 1
for ind in range(1,N-1):
for prev_num in range(21):
if dp[ind-1][prev_num]:
for new_num in [prev_num+arr[ind],prev_num-arr[ind]]:
if 0<=new_num<=20:
dp[ind][new_num] += dp[ind-1][prev_num]
print(dp[N-2][arr[-1]])
매번 어려운 DP 문제이다.
여기서 제일 헷갈렸던것은 인덱스였다.
먼저 dp의 행은 주어진 입력의 몇번째 index에서의 행해진 것인지 나타낸다.
그리고 열은 이 문제는 0~20 사이의 값만 있으므로, 21개의 열을 미리 만들어줬다.
먼저 dp를 0으로 초기화 시킨다.
그리고 dp[0][arr[0]] = 1로 초기화 한다.
가장 첫번째 숫자는 무조건 더해져야하기 때문이다.
그리고 그 다음부터는 0~21 까지를 prev_num으로 반복문을 돌리고 현재 ind의 arr값과 더했을때
0~20 사이이면 현재 ind의 새로운값에 더해주면 된다.
그리고 이 모든 행위는 N-2번 인덱스에서 종료되기 때문에, 출력할때 [N-2][arr[-1]]을 해주도록 하자.
# 실패한 방법
N,M = map(int,input().split())
arr = [list(map(int,list(input()))) for _ in range(N)]
result = 0
max_size = min(N,M)
for x in range(N):
for y in range(M):
if result == max_size:
break
if arr[x][y] == 1:
for sizes in range(result,max_size+1):
temp = 0
for dx in range(sizes):
for dy in range(sizes):
if 0<=x+dx<N and 0<=y+dy<M:
temp += arr[x+dx][y+dy]
if temp == sizes**2:
result = sizes
else:
break
print(result**2)
처음에 단순하게 현재의 max_size만큼을 각 위치에서 탐색을 해서 갱신해주는 방식을 했다. 이렇게 하니 시간 초과가 나왔다.
N,M = map(int,input().split())
arr = [[0]*(M+1)]
for _ in range(N):
arr.append([0]+list(map(int,list(input()))))
result = 0
max_size = min(N,M)
for x in range(1,N+1):
for y in range(1,M+1):
if arr[x][y]:
arr[x][y] = min(arr[x-1][y],arr[x][y-1],arr[x-1][y-1])+1
result = max(arr[x][y],result)
if result == max_size:
break
print(result**2)
1
1
1
1
위와 같은 정사각형이 있으면, 우하단을 기준으로 상하, 대각선이 전부 1이어야만 정사각형이 모양이된다. 만약 3개 중 하나라도 0이 있으면 크기가 2인 정사각형이 모양이 안된다. 그러므로 여기서 될수 있는 정사각형의 크기는 2이다.
1
1
1
2
이걸 좀 더 확장해서 3*3를 그려보도록 하자.
1
1
1
1
1
1
1
1
1
위와 같이 있다고 했을때 행과 열 중 0인 곳은 크기가 1를 초과하는 것을 못 만드므로 예외로 하겠다. 그러면 실질적으로 1,1 부터 탐색을 한다.
1
1
1
1
2
2
1
2
3
위와 같은 로직으로 하면 다음과 같이 우하단이 3이 되는 것을 알 수 있다
1
1
1
0
1
1
1
1
1
이렇게 한군데가 비어있으면
1
1
1
0
1
2
1
1
2
이렇듯 우하단이 2가 되는 것을 알 수 있다.
그러므로 이 문제는 (x,y) 좌표 기준으로 (x-1,y),(x,y-1),(x-1,y-1)의 값의 최소값에 + 1을 해주면 된다.
그리고 저장된 값 중에서 가장 큰 값이 이 행렬에서 제일 큰 정사각형이므로, 제곱을 해서 출력을 하면 된다.
# 2225번 합분해
N,K = map(int,input().split())
dp = [[1]*(N+1) if i==0 else [0]*(N+1) for i in range(K)]
for ind in range(1,K):
for prev_num in range(N,-1,-1):
for current_num in range(N,-1,-1):
if prev_num + current_num <=N:
dp[ind][prev_num+current_num] += dp[ind-1][prev_num]
print(dp[K-1][N]%1000000000)
K 번을 더햇 N이 나오는 경우이므로, DP를 (N+1)*K 형태로 만들어 놨다. 그래서 이전 행에서의 prev_num과 현재의 current_num을 더해서 N을 넘지 않는 경우 새로운 행에 그 횟수를 저장해주는 방식을 해주었다.
N,K = map(int,input().split())
dp = [[1]*(N+1) if ind==0 else [0]*(N+1) for ind in range(K)]
for k in range(1,K):
for num in range(N+1):
dp[k][num] = (dp[k-1][num] + dp[k][num-1])%1000000000
print(dp[K-1][N])
위의 방식대로 풀어도 시간내에 통과하지만 점화식을 구하면 좀 더 쉽게 구할 수 있다.
DP[K][N] = DP[K-1][N] + DP[K-1][N-1] + .... + DP[K-1][0] 이다.
DP[K][N-1] = DP[K-1][N-1] + DP[K-1][N-2] + .... + DP[K-1][0] 인 것을 알 수 있따.
이것을 봐보면 DP[K][N] = DP[K-1][N] + DP[K][N-1]인 것을 알 수 있다.
# 1937 욕심쟁이 판다 실패(Fail)
def dfs(x,y):
global N
stack = [(x,y,0)]
last_direction = []
while stack:
cx,cy,distance = stack.pop()
flag = True
for i in range(4):
nx = cx + dx[i]
ny = cy + dy[i]
if 0 <= nx<N and 0<=ny<N:
if bamboo[cx][cy] < bamboo[nx][ny]:
if dp[nx][ny] == -1:
stack.append((nx,ny,distance+1))
else:
if distance + dp[nx][ny] + 1 > dp[x][y]:
dp[x][y] = dp[nx][ny] + distance + 1
flag = False
if flag:
if dp[x][y] < distance + 1:
dp[x][y] = distance + 1
N = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
bamboo = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*N for _ in range(N)]
result = - 1
for x in range(N):
for y in range(N):
if dp[x][y] == -1:
dfs(x,y)
print(max(map(max,dp)))
이 문제를 단순하게 DFS로 풀면 시간 초과가 날수 밖에 없다. 왜냐하면 입력이 최대가 500*500 이므로, dp를 통해 이미 탐색한 값들을 저장해놓는 과정이 필요하다. 위의 코드는 시간초과가 난 코드이다.
dp를 사용하긴 했지만, 각 (x,y) 축에서 dfs를 하지만, 이 이동경로에 있는 좌표들에 대해서 이미 한번 측정한 값인데, 다시 한번 dp를 측정해야하는 것이다.
import sys
def dfs(x,y):
if dp[x][y] != -1:
return dp[x][y]
else:
dp[x][y] = 1
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<N and 0<=ny<N:
if bamboo[nx][ny]>bamboo[x][y]:
distance = dfs(nx,ny) + 1
dp[x][y] = max(distance,dp[x][y])
return dp[x][y]
N = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
bamboo = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*N for _ in range(N)]
result = - 1
for x in range(N):
for y in range(N):
if dp[x][y] == -1:
dfs(x,y)
print(max(map(max,dp)))
재귀를 이용한, 이동 경로에 대해서 전부 한번에 업데이트를 해주는 것이다.
최초 이동경로에서 (x0,y0) = > (x1,y1) => (x2,y2) => ...=>(xn,yn) 각 경로마다 최대로 갈수 있는 이동경로들을 저장해준다. 그리고 return된 값에 + 1을 해줘 해당 칸에 갔을때의 이동거리를 측정해주고, 최대값을 갱신해주면 된다.
이렇게 하면 장점은 어느 곳에서 한번 방문했던 곳은 더 이상 dfs를 하지않고 해당 위치에서의 최대값을 반환해주는 것이다.
이 문제는 각 위치마다의 최대경로를 구하는 로직과, 그걸 이용해서 시간복잡도를 줄이는게 중요한 문제였다.
그러니 실질적으로, 내힘으로 푼 문제라 할순 없지만, 내가 잘 모르는 Tree-dp에 관련된 문제이고, 코드를 분석하면서, 이러한 문제 유형에 대해서 경험해보기 위해서 풀었다.
자세한 설명을 원하시는 분은 상단에 링크된 유튜브와 카카오 공식 블로그를 참조하길 바란다.
기본적인 풀이는 tree-dp에 관련된 문제였다. dp를 tree에 적용시킨 거고, dfs를 재귀방식으로 해서 푼 문제로 생각했다..
먼저 들어온 links에 대해서 부모노드에 자식노드를 추가해주는 작업을 했다.
그리고 index가 전부 1부터 시작하기 때문에 풀이의 용이함을 위해, sales 앞에 0을 추가해주었다.
이 상태에서 dfs를 통해, 매출하락 최소화를 구하는 작업을 해줬다.
loss_sale 이란 변수는 해당 노드가 워크샵에 참여유무에 따른 매출하락을 저장해놓은 변수이다.
ex ) loss_sale[x][0] 은 x번 노드가 워크샵에 참석하는 경우
loss_sale[x][1] 은 x번 노드가 워크샵에 참석하지 않는 경우
dp는 작은단위부터 해야된다고 생각해서, 가장 끝단부터 하겠다.
1) 리프노드일 경우
리프노드 일 경우엔, 자기자신이 참석하는 거 외에는 loss_sale을 갱신해줄만한 요소가 없다.
loss_sale[leaf_node][0] = sales[leaf_node] 를 넣어주고 return 해주면 된다.
2) 리프노드가 아닐 경우
리프노드가 아닐경우, 그 노드들은 팀원이면서 팀장이다. 여기서는 dfs를 들어갔을때, 팀장노드인 시점에서 들어가므로, 팀장노드라고 부르겠다.
2-1) 팀장노드가 참석하는 경우
> 팀장노드가 참석하는 경우에는 팀원노드들이 어떤 상태인지 상관 없기 때문에, 각 자식노드들의 참석 불참석했을 때 둘 중 최소값을 더해주면 된다.
> 그리고 마지막으로 팀장노드의 매출 값을 저장해주면 된다.
즉, 각 팀원노드마다 min(loss_sale[팀원노드][0],loss_sale[팀원노드][1]) 를 구해서 더해주고, 마지막에 팀장의 sales를 더해주면 된다.
2-2) 팀장노드가 참석하지 않는 경우
> 팀장 노드가 참석하지 않는 경우엔, 팀원 노드들 중에 한명이 무조건 참석을 해야한다. 그렇다면 매출하락폭이 최소화가 될려면 불참이었을때와 참여했을때의 loss_sale을 비교해서 그 차이가 최소값인 것을 찾아서 그 팀원노드을 선택하면 된다. 그 팀원이 불참이였다가, 참여로 전환시키는 것이기때문에 그 값을 더해주면 된다.
> 여기서 max(0,atamp_loss)라고 해준 이유는 카카오 공식문서에서 나온 설명 마지막 부분과 부합된다.
만약 팀원노드 A가 있다고 했을때,
팀원노드 A가 팀장인 팀에서 최소가 되는 경우가, 팀원노드 A가 참석을 했을 때라고, 하면,
위에서 구한, loss_sale[팀원노드 A의 부모노드][0]에 포함이 되어있을것이고, 이미 A라는 팀원이 참석한것이기
때문에, 더해줄 필요성이 없다.
그래서 팀원노드 A의 loss_sale은 참석했을때 loss_sale[팀원노드A][0] 보다 loss_sale[팀원노드A][1]이
더 클 것이기 때문에 음수가 나오므로, max를 통해 0과 비교하여 음수를 방지해 주는 것이다.
> 이렇게 참석과 불참석의 차이가 최소가 되는 노드를 선택하고 그 값에 팀장노드가 참석했을때의 값에서
팀장노드가 참석을 안하기 때문에, 팀장노드의 매출을 빼주면 된다.
위와 같은 과정을 거친 후 CEO인 1번노드의 loss_sale의 최소값을 출력해주면 된다.
이 문제는 풀이를 보면서 풀었지만, tree와 dp에 대한 개념이 잡히지 않고서는 쉽게 풀 수 없는 문제 인것같다.
평소에도 가장 어려워하는 알고리즘이 dp와 tree이기때문에, 어려웠고, 그 2개가 합쳐진거라 더 나에게 어려움으로 느껴졌다.
이 풀이를 보면서 느낀점은 dp를 풀때에는 소분화해서 풀어야 하고, 점화식을 찾아서 동적으로 해야한다.
상반기까지 남은기간이 얼마 안남았는데,
내가 평소에 약점인 tree, dp, 플로이드, prefix_sum, 투포인터,segement tree (거의 대부분이지만) 에 대해서 더 공부해야겠다.