Coding 공부

import sys
sys.setrecursionlimit(20000)
def input():
    return sys.stdin.readline().rstrip()
def trace(cur_node,prev_check):
    visited[cur_node] = False
    flag = 0
    if not prev_check:
        if dp[cur_node][0] < dp[cur_node][1]:
            result.append(cur_node)
            flag = 1
    for next_node in graph[cur_node]:
        if visited[next_node]:
            trace(next_node,flag)

def dfs(node):
    visited[node] = False
    child_node = []
    for next_node in graph[node]:
        if visited[next_node]:
            child_node.append(next_node)
    if not len(child_node):
        dp[node][1] = arr[node]

        return
    else:
        dp[node][1] += arr[node]
        for child in child_node:
            dfs(child)
            dp[node][0] += max(dp[child][1],dp[child][0])
            dp[node][1] += dp[child][0]



N = int(input())
arr = [0] + list(map(int,input().split()))

# 1이 선택 
# 0이 선택 x
dp = [[0 for _ in range(2)] for _ in range(N+1)]

graph = [[] for _ in range(N+1)]
visited = [True for _ in range(N+1)]
for k in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)


dfs(1)

print(max(dp[1]))


result = []
visited = [True for _ in range(N+1)]
trace(1,0)
result.sort()
print(*result)

어려웠던 문제였다. 트리dp를 활용해서 최적의 경우를 찾는 것은 많았지만, 그 최적을 만족하는 것을 trace를 하는 문제는 처음이라 푸는데 오래걸렸다.

dp라는 테이블을 만들고 (N+1)*2의 배열을 만들어 두었다.

여기서 1은 해당 노드를 선택했을때의 최대값

0은 해당 노드를 선택하지 않았을때의 최대값이다.

만약 리프노드이면 자신을 선택하는 조건이외에는 없을것이다.

그러므로 dp[leef_node][1] = arr[leef_node]를 넣어준다.

리프노드를 제외한 나머지 노드들은 0번 인덱스와 1번인덱스의 최대값을 구해야한다.

현재 노드를 선택했을때 즉 1번인덱스에는

현재 노드를 cur_node라고 했을때 arr[cur_node]를 더해줘야할것이다.

그리고 현재 노드를 선택했으므로, 자식노드들은 선택을 하지 못한다.

그러므로 dp[cur_node][1] += dp[child_node][0] 와 같이

자식 노드들의 선택하지않았을때의 값들을 전부 더해줘야한다.

그리고 현재 노드를 선택하지 않았을때에는

자식 노드를 선택하던지, 선택하지 않는것은 마음대로 할 수 있다.

그러므로 둘중 더 큰 값을 더해주면 된다.

이렇게 dp에 값을 누적시켜서 구하면

우리는 1번노드로 시작했기 때문에

1번노드의 dp에서 최대값을 구할 수 있다.

그러면 우리는 이 dp에서 어떤 노드들이 선택됬는지를 찾아봐야한다.

우리는 이전 노드에서 선택했는지 안했는지에 따라, 현재 노드를 선택할수 있는지 아닌지가 결정이 된다.

그래서 우리는 prev_check를 통해 문제를 해결했다. 위와 동일하게 하기 위해서 0일때에는 부모노드를 선택하지 않았다.

1일때에는 부모노드를 선택했다이다.

만약 부모노드를 선택하지 않았을때에는, 우리는 지금 있는 현재노드를 선택할지 안할지를 결정지을수 있다.

그 결정방법은 dp에 저장된 값을 비교를 해서, 우리가 선택하지 않았을때보다 선택했을때의 값이 더 크면,

그때 현재노드를 선택을 하고, flag를 1로 바꿔준다. 현재노드를 선택을 했으므로, result에 추가 시켜준다.

그리고 재귀를 통해 모든 노드들에 대해 탐색을 해주면 된다.

이 문제는 최대값을 구하는 것 뿐만 아니라, 그 경우의 수가 만들어지는 것을 찾는데 더 어려움을 겪었다.

트리 dp와 관련된 문제들을 좀 더 연습해야겠다.

from itertools import combinations

def dfs(cu_val,cnt,pick_list):
    global result
    if cnt == 0:
        result = max(result,cu_val*sum(pick_list))
        return cu_val * sum(pick_list)
    else:

        idx_list = range(len(pick_list))
        for pick_cnt in range(1,len(pick_list)-cnt+1):
            for comb in combinations(idx_list,pick_cnt):
                copy_pick_list = pick_list[:]
                comb = list(reversed(comb))
                temp_sum = 0
                for idx in comb:
                    temp_sum += copy_pick_list.pop(idx)                
                dfs(cu_val*temp_sum,cnt-1,copy_pick_list)







N = int(input())

arr = list(map(int,input().split()))

p_cnt,a_cnt = map(int,input().split())


result = 0
dfs(1,a_cnt,arr)
print(result)

생각 난대로 풀었더니, 운좋게 풀린 문제였다.

이 문제에서 주의해야할 점은 숫자는 순서에 상관없이 배치를 해도 되고, 더하기와 곱셈의 우선순위가 같다.

이 2가지를 주의해야한다.

이 문제를 풀때 최대값을 구할때 중요하다고 생각한 것이 곱셈이라고 생각했다.

곱셈을 기준으로 구역을 나누고, 그 사이에 숫자를 집어넣으면 된다고 생각했다.

즉 곱셈의 기호가 3개가 주어진다면

이렇게 4구역으로 나눌수 있다고 생각했다.

즉 주어진 숫자들을 4팀으로 나누면 된다.

그리고 각 팀은 최소1명이상 이어야만 한다라는 조건을 만족해야한다.

그런 방식으로 숫자를 나눠주고, 나뉜 숫자들을 합을 계속 곱해주면서 idx가 마지막까지 올때까지 해주었다.

위의 dfs라는 함수가 그것을 의미한다.

현재 위치에서 최대로 뽑을 수 있는 숫자는 남은숫자 - 곱셈 기호가 남은개수 만큼 뽑을 수 있다.

그렇게 1개부터 (남은숫자 - 곱셈기호가 남은 개수)까지 반복문을 돌리면서

숫자들을 뽑아서 재귀를 해주었다.

# edenooo님 코드 복기
from itertools import permutations
def dfs(idx,cnt,position,num_list):
    global result
    if (cnt+N-1-idx)<Q:
        return
    if idx == N-1:
        position.append(idx)
        mul_val = 1
        sum_val = 0
        cu_idx = 0
        for mul_idx in position:
            while (cu_idx<=mul_idx):
                sum_val += num_list[cu_idx]
                cu_idx += 1
            mul_val *= sum_val
            sum_val = 0
        result = max(result,mul_val)
        position.pop()
        return
    dfs(idx+1,cnt,position,num_list)
    position.append(idx)
    if cnt+1<=Q:
        dfs(idx+1,cnt+1,position,num_list)
    position.pop()
N = int(input())
arr = list(map(int,input().split()))
result = 0
arr.sort()

P,Q = map(int,input().split())
for perm in permutations(arr):
    dfs(0,0,[],perm)
print(result)

이 풀이는 edenooo님의 풀이이다. 기본적인 아이디어는 비슷하다고 볼 수 있다.

여기서는 모든 숫자들이 나올 수 있는 배치들을 만들어두고, 곱셈의 위치를 변경시켜서 해주는 방식으로 해주었다.

import sys

def input():
    return sys.stdin.readline().rstrip()

def dfs(idx):
    if idx >= N:
        return 0

    if dp[idx] != -1:
        return dp[idx]
    max_value = 0
    for string_key in score_dict.keys():
        score,len_string = score_dict[string_key]
        if idx + len_string-1<N:
            for check_idx in range(len_string):
                if input_string[check_idx+idx] != string_key[check_idx]:
                    break
            else:
                max_value = max(max_value,score + dfs(idx+len_string))
    max_value = max(max_value,1+dfs(idx+1))
    dp[idx] = max_value
    return dp[idx]
                

input_string = input()
N = len(input_string)
M = int(input())
score_dict = {}
for _ in range(M):
    string,score = input().split()
    score_dict[string] = [int(score),len(string)]



dp = [-1]*(N+1)

print(dfs(0))

문제를 푼 방식은 다음과 같다.

문제에 주어진 문자열들을 문자열을 key로 하고, 점수와 길이를 value로 하는 dictionary에 넣어둔다.

그리고 0번인덱스부터 재귀를 돌면서

현재 위치에서부터 문자열이 일치하는 경우에 재귀를 하면서 최대값을 구한다.

그리고 일치하지 않을때를 위해, dfs(idx+1)+1 현재위치의 문자열만을 제거했을때도 구해주면된다.

그리고 dp값을 변환시켜주면 된다.

import sys

input = sys.stdin.readline

def dfs(state,order_cnt):
    global result
    if order_cnt >= P:
        result = min(result,dp[state])
        return
    else:
        if dp[state] > result:
            return

        else:
            for cu_node in range(N):
                if state & 1<<cu_node:
                    for next_node in range(N):
                        if not state & 1<<next_node and dp[state|1<<next_node] > dp[state] + arr[cu_node][next_node]:
                            dp[state|1<<next_node] = dp[state] + arr[cu_node][next_node]
                            dfs(state|1<<next_node,order_cnt+1)



N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]


state_string = input()
state = 0
P = int(input())
order_cnt = 0
stack = []
result = float('inf')
for i in range(N):
    if state_string[i] == 'Y':
        state += 1<<i
        order_cnt += 1
        stack.append(i)
dp = [float('inf') for _ in range(2**N+1)]
dp[state] = 0
if order_cnt == P:
    print(0)
else:
    dfs(state,order_cnt)
    if result == float('inf'):
        print(-1)
    else:
        print(result)

재귀를 이용해서 문제를 풀었다.

먼저 비트로 각 발전소의 상태를 구분해주었다.

발전소의 위치와 비트의 위치를 동일시해서, 0번째 비트가 1이면, 0번 발전소가 켜져있는것이다.

그러므로 우리는 마지막으로 들어온 입력을 이용해 현재 발전소의 상태를 비트로 표현을 해준다.

그리고 dp라는 테이블에 발전소를 고치는 최소값을 갱신해주기 위해, 만들어두었다.

그 크기는 state의 크기이므로 2**N까지가 필요하다. 

미리 만들어놓은 상태에서 dfs 함수를 통해 재귀를 하면서 문제를 푸는데 접근을 했다.

2중 포문을 돌면서 dfs에 들어온 state를 통해, 현재 켜져있는 발전소를 구분을 해준다.

그리고 발전소가 켜져있으면 두번째 for문을 통해, 켜지지 않은 발전소를 구하고, 현재 state에서 발전소를 켰을때 비용이 더 작은 경우에

추가적으로 dfs를 하는 작업을 해주었다.

그리고 문제에 주어진 P보다 크거나 같으면 종료되도록 함수를 짰다.

import sys

input = sys.stdin.readline

def dfs(state,order_cnt):
    if dp[state] != -1:
        return dp[state]
    if order_cnt >= P:
        dp[state] = 0
        return 0
    else:
        min_value = float('inf')
        for cu_node in range(N):
            if state & 1<<cu_node:
                for next_node in range(N):
                    if not state & 1<<next_node:
                        min_value = min(min_value,dfs(state|1<<next_node,order_cnt+1) + arr[cu_node][next_node])
        dp[state] = min_value
        return dp[state]

N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]


state_string = input()
state = 0
P = int(input())
order_cnt = 0
for i in range(N):
    if state_string[i] == 'Y':
        state += 1<<i
        order_cnt += 1
dp = [-1 for _ in range(2**N+1)]
if order_cnt >= P:
    print(0)
elif order_cnt == 0:
    if P:
        print(-1)
    else:
        print(0)
else:
    result = dfs(state,order_cnt)
    if result == float('inf'):
        print(-1)
    else:
        print(result)

좀 더 깔끔한 풀이는 다음과 같다.

return 되는 값을 이용해 바로 출력이 가능하게 하는것이다.

기본 적인 원리는 같으며, 반환되는 값을 비교를 해서 최저값을 갱신을 해주는 것이다.

그리고 조건을 만족했을때에는 0을리턴하는식으로 해주는 것이다.

이 풀이가 dp라는 테이블을 좀더 생산적으로 쓰면서 풀 수 있는 방식이다.

import sys

def check(idx,cnt):
    global result
    if idx == N:
        result = max(result,cnt)
        print(result)
        exit()
        return
    else:
        for next_idx in range(idx+1,N,2):
            if dp[idx][next_idx]:
                check(next_idx+1,cnt+1)
input = sys.stdin.readline

N = int(input())

arr = list(map(int,input().split()))

dp = [[ True  if i == j else False for j in range (N)]  for i in range(N)]
for i in range(N-1):
    if arr[i] == arr[i+1]:
        dp[i][i+1] = True

for i in range(2,N):
    for j in range(N-i):
        if arr[j] == arr[j+i] and dp[j+1][j+i-1]:
            dp[j][j+i] = True

max_num = N//2
result = -1
check(0,0)
print(result)

이 문제는 boj.kr/10942에서 풀었던 전체 배열에 대한 팰린드롬의 dp를 구해놓은 상태로 풀었다.

먼저 전체 배열의 대한 팰린드롬 상태를 dp에 저장시켜놓는다.

그리고 우리는 check를 해주면 된다.

우리는 짝수개 만큼 나눌수 있다.

그러면 우리는 현재 위치에서 짝수번째 떨어진 위치의 dp 상태값을 통해 팰린드롬이면 재귀를 통해

N번째 index에 도착할때까지 계속해준다.

그리고 최초로 도착을 했을때가 가장 최대 짝수팰린드롬이므로, 그때 값을 출력해주면 된다.

왜냐하면, 우리는 2칸단위부터 자르기 때문에,

가장 먼저 도착하는 것이, 가장 많이 자른것이기 때문이다.

이 문제는 이렇게 dp로 푸는 방식말고도 그리디방식으로도 푸는 방식이 있다하지만, 배움이 부족해,

그 풀이는 정확히 이해하지 못했다.

import sys
from collections import deque
input = sys.stdin.readline


def bfs(point,dis_list,flag):
    dis_list[point[0]][point[1]] = arr[point[0]][point[1]]
    dx = [-1,0]
    dy = [0,1]

    stack = deque()
    stack.append((point[0],point[1]))

    while stack:
        x,y = stack.popleft()

        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]*flag
            if 0<=nx<N and 0<=ny<M:
                if dis_list[nx][ny] < dis_list[x][y] + arr[nx][ny]:
                    dis_list[nx][ny] = dis_list[x][y] + arr[nx][ny]
                    stack.append((nx,ny))
        


N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
INF =float('inf')
start_distance = [[-INF for _ in range(M)] for _ in range(N)]
end_distance = [[-INF for _ in range(M)] for _ in range(N)]

start_point = (N-1,0)
end_point = (N-1,M-1)
bfs(start_point,start_distance,1)
bfs(end_point,end_distance,-1)

max_value = -INF

for i in range(N):
    for j in range(M):
        if start_distance[i][j] + end_distance[i][j] > max_value:
            max_value = start_distance[i][j] + end_distance[i][j]
print(max_value)

 이 문제는 저는 BFS를 이용해서 풀었다.(근데 아직 푼사람이 적은지 solved.ac 기준에는 다이나믹 프로그래밍 밖에 없다.)

boj.kr/2206 문제와 비슷한 방식으로 풀었다.

이 문제를 봐보면 상승이나 하강은 특정한 방향으로 밖에 가지 못한다.

이 점을 이용해서 우리는 특정지점 (x,y)까지의 최대값을 bfs를 이용해 갱신할 수 잇을것이다.

그래서 나는 (N-1,0)에서 상승을 시작하므로, 이 지점을 시작으로 갈수 있는 모든지점에 대해, bfs를 돌려 최대값을 갱신을 해주었다.

똑같은 방식으로 (N-1,M-1) 위치로 하강을 해야하므로, 이 위치에서 하강의 반대방향으로 BFS를 돌리면서 최대값을 갱신을 해주었다.

그러면 우리는 상승을 할때의 각 지점의 최대값 하강을 할때의 각 지점의 최대값을 가지고 있는 행렬을 가지게 되었다.

이 두 행렬의 합을 전체 탐색을 하면서, 가장 큰 값을 출력해주면 되는 문제이다.

import sys

def find_agent(agent,task):
    if agent == N:
        return 1
    
    if dp[task] != -1:
        return dp[task]

    for i in range(N):
        if not (task & 1<<i):

            temp = find_agent(agent+1,task|1<<i)*arr[agent][i]/100
            if temp > dp[task]:
                dp[task] = temp
    
    return dp[task]
input = sys.stdin.readline
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]


dp = [-1 for _ in range(2**N+1)]




find_agent(0,0)

print(dp[0]*100)

문제를 푸는방식은 다음과 같다. 

각 task를 비트로 구분을 하게 한다.

이 문제에서 최대 20개의 임무가 있으므로, 2^20으로 비트를 구분해낼수 있다.

이러한 점을 이용해, 각자리의 비트는 그와 대응되는 일을 맡는것으로 가늠할 수 있다.

그래서 우리는 재귀를 이용해, 현재까지 선택된 task에서 선택되지 않은 task를 선택해 재귀를 한뒤,

그 결과값들을 최대값으로 갱신을 해주면 되는 문제이다.

또한 중복되는 일을 방지하고자, task별로 값을 저장한뒤에 그 값이 초기값이 아니면 되돌려주는 작업을 해주었다.

import sys

sys.setrecursionlimit(100000)


def dfs(x,y):
    if visited[x][y]:
        return INF
    elif dp[x][y] >0:
        return dp[x][y]
    else:
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]*int(arr[x][y])
            ny = y + dy[i]*int(arr[x][y])
            if 0<=nx<N and 0<=ny<M and arr[nx][ny].isdigit():
                dp[x][y] = max(dp[x][y],dfs(nx,ny) + 1)
                if dp[x][y] == INF:
                    return INF
        visited[x][y] = False
    return dp[x][y]

            





dx = [-1,1,0,0]
dy = [0,0,1,-1]
N,M = map(int,input().split())
INF = float('inf')
arr = [list(input()) for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
dp = [[0 for _ in range(M)] for _ in range(N)]



result = dfs(0,0)

if result == INF:
    print(-1)
else:
    print(result+1)

 DP와 DFS를 활용한 문제 였다. 이 와 비슷한 문제를 풀어본 경험이 있었기 때문에 수월하게 풀 수 있었다.

여기서 문제에서 동전을 무한번 움직일때 -1을 출력한다는 것은 한번 방문을 했던 곳을 재귀 중에 방문을 하면, 들렸던 

장소에서 현재까지 오는 것이기때문에, 무한번 반복할 수 있다는 생각으로 만들어줬다.

그리고 입력과 똑같은 크기의 DP를 만들어서 해당 값이 초기값인 0이 아닌 다른 값이 있는 것은 해당 위치에서

탐색을 끝낸 것이기 때문에 초기값이 아닐때에는 바로 넘겨주는 것을 구현을 했다.

기본적이 풀이 방식은 다음과 같다.

왼쪽 위에서부터 탐색을 하면서, DFS를 처음 들어갈때 방문을 한곳인지 아닌지를 체크한다. 방문을 안한 곳이면,

방문을 체크해주고, 현재 위치에서 동서남북으로, 움직임이 가능한 경우를 탐색한다.

그리고 가능할때 그 방향으로 DFS를 하면서 한번 움직인 것이기 때문에 + 1을 해준다.

이렇게 재귀를 하면서 현재의 DP값과 최대값을 비교해서 저장을 해준다.

그리고 이 4방향을 다 둘러본것은 전부 탐색을 한 것이기 때문에 방문을 초기화 해준다.

그리고 현재 DP 값을 돌려주면 된다.

이렇듯 방문을 체크하는 리스트와 현재 위치에서의 최대값을 저장해주는 DP를 활용해서 풀 수 있는 문제였다.