Coding 공부

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()


def LCS(X,Y):
    if depth[X] != depth[Y]:
        if depth[X]>depth[Y]:
            X,Y = Y,X
        for i in range(MAX_NODE-1,-1,-1):
            if (depth[Y]-depth[X] >= (1<<i)):
                Y = parents[Y][i]
    if X == Y:
        return X
    if (Y != X):
        for i in range(MAX_NODE-1,-1,-1):
            if parents[X][i] != parents[Y][i]:
                X = parents[X][i]
                Y = parents[Y][i]
    return parents[X][0]
def tree_make(idx,cur_node,node_cnt,parent_idx):
    if idx == len(binary_list):
        return
    if binary_list[idx] == 0:
        node_cnt += 1
        cur_node = node_cnt
        binary_search[idx+1] = cur_node
        tree[cur_node].visited.append(idx+1)
        tree[cur_node].parent = parent_idx
        depth[cur_node] = depth[parent_idx] + 1
        parents[cur_node][0] = parent_idx
        if cur_node != 1:
            parent_node = tree[cur_node].parent
            if tree[parent_node].left == None:
                tree[parent_node].left = cur_node
            else:
                tree[parent_node].right = cur_node
        tree_make(idx+1,cur_node,node_cnt,cur_node)
    else:
        binary_search[idx+1] = cur_node
        tree[cur_node].visited.append(idx+1)
        cur_node = tree[cur_node].parent
        tree_make(idx+1,cur_node,node_cnt,cur_node)



class Node():
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.parent = None
        self.visited = []

N = int(input())
binary_list = list(map(int,list(input())))
i,j = map(int,input().split())
tree = [Node(i) for i in range(N+1)]
MAX_NODE = 15
binary_search = [0 for _ in range(len(binary_list)+1)]
depth = [0 for _ in range(N+1)]
parents = [[0 for _ in range(MAX_NODE)] for _ in range(N+1)]

tree_make(0,0,0,0)
for par_idx in range(1,MAX_NODE):
    for k in range(1,N+1):
        parents[k][par_idx] = parents[parents[k][par_idx-1]][par_idx-1]

X,Y = binary_search[i],binary_search[j]

result_node = LCS(X,Y)
print(*tree[result_node].visited)

LCA를 이용해서 풀어본 처음 문제였다.

LCA를 공부하면서 푼 풀이이다. 

LCA에 대한 자세한 설명은

https://jason9319.tistory.com/90    https://www.crocus.co.kr/660    https://m.blog.naver.com/kks227/220820773477  https://velog.io/@lre12/LCA-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Lowest-Common-Ancestor

위의 사이트들을 참조하길 바란다.

LCA를 공부하면서, 이해하다가 막혔다가 푼 부분을 적으면 다음과 같다.

1. 부모를 저장하는 dp 테이블에는 해당 노드의 모든 부모를 저장하는 것이 아닌 2^k번째 부모들만 압축해서 저장해놓는것이다.

2. 위의 파생이지만, 그렇기 때문에, 두 높이의 차이가 1<<i 즉 2^i 차이가 나면, i만큼 올려주면 되는것이다.

3. 그리고 두 높이가 같고, 서로 다르다면, k번째 위치부터 다른 값까지 한꺼번에 올려버린다.

  즉, dp[node1][k] , dp[node2][k] 는 다르지만, dp[node1][k+1], dp[node][k+1]이 같으면

   각 노드들의 2^k + 1 ~ 2^(k+1) 사이에 최소 공통 조상이 있을 것이다. 이 부분을 주의하면 된다.

4. 또한, 첫번째에서 말한것처럼 2^k번째 만 저장을 시켜놓은것이기때문에

    2^(k+1) = 2^k + 2^k 이다.

    2^k = 2^(k-1) + 2^(k-1) 이므로,

dp[node][k] = dp[ dp[node][k-1] ] [k-1] 으로 하면 LCA의 해당 노드들의 모든 공통조상부모에 대해서 저장시킬수 있다.

위의 것들이 윗 링크들을 공부하면서 제가 깨달은 부분이다.

인제는 문제로 돌아가서 

여기서 문제에 주어진 비트를 트리구조로만 바꾸면 우리는 위에서 배운 LCA를 적용시키면 된다.

저는 여기서 이 문제를 해결하기 위해 Node라는 클래스를 만들어놨습니다.

해당 Node에는 총 5가지의 파라미터가 있습니다.

data는 이 노드의 번호를 나타내고,

left는 왼쪽 자식번호

right는 오른쪽 자식번호

parent는 부모 번호

visited는 우리가 주어진 비트에서 몇번재 비트에서 이 노드를 방문했는지 표시르 위한 것입니다.

저는 tree_make라는 재귀함수를 만들어 이 문제를 해결했습니다.

입력 parameter는 4가지가 있고, idx는 현재 입력으로 주어진 비트의 몇번째 idx인지를 나타냅니다.

cur_node는 현재 노드의 번호입니다.

node_cnt는 지금까지 생성된 노드의 개수입니다.

parent_idx는 부모 노드의 번호입니다.

비트에서 우리가 0을 만나면 최초로 생성되는 노드로 진입하게 되는겁니다.

그래서 node_cnt를 1을 늘려주고, cur_node를 node_cnt로 바꿔줍니다.

그러면 우리는 현재 부모노드의 정보를 알고 있으므로,

부모노드의 left와 right 중 빈 순서대로 넣어주면 됩니다.

그리고 1을 만나게 되면 우리는 현재 방문하고 있던 노드에서 다시 되돌아가서 부모노드로 가야합니다.

그렇기 때문에 cur_node를 부모노드로 치환시키고, 재귀를 반복하면 됩니다.

즉 0을 만나면 새로운 노드가 생성이되고,

1을 만나면 부모노드로 되돌아간다는 점만 기억을 하면, 문제에서 주어진 비트를 트리로 만들 수 있습니다.

코드가 깔끔하지 못해, 다른 분들의 코드를 보는 것을 더 추천합니다.

위와 같은 작업을 해서 비트를 트리구조로 바꾼뒤에 LCA을 적용시키면 이 문제를 해결 할 수 있습니다.

LCA와 관련된 문제를 처음 풀어보았기에, 헷갈리던 점도 많았고, 트리에 대해 숙달되지 못했기에,

비트를 트리로 구현하는데에 오래 걸린 문제였습니다.

매번 트리와 관련된 문제가 나오면 문제를 해결하는데 시간이 오래걸리는 것 같은데,

이 부분을 숙달하는데 더 노력을 해야할 것 같습니다.

import sys
from collections import defaultdict,deque
def input():
    return sys.stdin.readline().rstrip()
N,M = map(int,input().split())
material_dict = {'-1':True}
# dict를 고정시키는게 문제
material_pay = [float('inf') for _ in range(10000)]
queue = deque()
for k in range(N):
    name,pay = input().split()
    material_dict[name] = k+1
    material_pay[k+1] = int(pay)
    queue.append(material_dict[name])



graph = defaultdict(list)


total_recipe_list = [input() for _ in range(M)]
recipe_cnt = defaultdict(int)
recipe_dict = defaultdict(list)
recipe_order = defaultdict(list)
total_recipe_list.sort()

for total_recipe in total_recipe_list:
    complete_name,arg = total_recipe.split('=')
    recipe = arg.split('+')
    if material_dict.get(complete_name):
        complete_idx = material_dict[complete_name]
    else:
        complete_idx = len(material_dict.keys())
        material_dict[complete_name] = complete_idx

    recipe_idx = (complete_idx,recipe_cnt[complete_idx])
    recipe_cnt[complete_idx] += 1
    temp_set = set()
    temp = defaultdict(int)
    for res in recipe:
        cnt,name = int(res[0]),res[1:]
        if material_dict.get(name):
            name_idx = material_dict[name]
        else:
            name_idx = len(material_dict.keys())
            material_dict[name] = name_idx
        if recipe_idx not in graph[name_idx]:
            graph[name_idx].append(recipe_idx)
        temp_set.add(name_idx)
        temp[name_idx] += cnt
    recipe_order[complete_idx].append(temp_set)
    recipe_dict[complete_idx].append(temp)

flag = True
        
total_len = len(material_dict) - 1
cnt = 0
while queue:

    name_idx = queue.popleft()
    if graph.get(name_idx):
        for next_idx,recipe_idx in graph[name_idx]:
            # 다시 들어왔을때 문제
            if name_idx in recipe_order[next_idx][recipe_idx]:
                recipe_order[next_idx][recipe_idx].remove(name_idx)


            if not len(recipe_order[next_idx][recipe_idx]):
                temp = 0

                for mat,val in recipe_dict[next_idx][recipe_idx].items():
                    temp += material_pay[mat]*val
                if material_pay[next_idx] > temp:

                    queue.append(next_idx)
                    material_pay[next_idx] = temp
                
if material_dict.get('LOVE'):
    result = material_pay[material_dict['LOVE']]
    if result == float('inf'):
        print(-1)
    elif result > 1000000000:
        print(1000000001)
    else:
        print(result)
else:
    print(-1)

이 문제는 여러번 틀렸던 문제였다.

풀면서 주의해야할 점은 다음과 같다.

처음에 주어지는 재료의 개수가 N의 최대가 50이라고 했지

모든 레시피에서 주어지는 재료의 개수가 50인게 아니다.

그래서 이걸 저장을 할때에는 넉넉하게해줘야한다.

두번째 여기서는 사이클같은 구조가 생길수 있다.

즉 위상정렬에서 한번 검사했던 노드이지만,

들어간 재료 중 하나가 최저값이 갱신이 되서, 현재 만들어지는 재료가 더 줄어둘수도 있다.

세번째 들어오는 입력에서 같은 재료가 여러번에 나뉘어서 들어 올수 있다.

네번째 같은 재료를 만드는 레시피가 여러종류가 있을 수 있다.

그래서 이 문제를 풀때 기본 컨셉은 다음과 같다.

각 완성재료를 만드는 전체 레시피들은 recipe_dict에 넣어줬다.

같은 완성재료를 만드는 방법이 여러개라면, recipe_cnt로 각 완성재료를 만드는 n번째 idx 이런식으로 구분을 해주었다.

그리고 위상정렬을 위해 order를 저장해주는 방식은

recipe_order[완성재료][레시피idx] 에 들어간 재료를 set으로 저장을 해주었다.

그리고 가장 중요한 그래프는 다음과 같이 저장을 해주었다.

graph라는 dictionary에 한 완성재료를 만드는 부품에 각각 (완성재료,완성재료를 만드는 레시피의 번호)를 저장시켜주었다.

그리고 material_dict은 재료명 대신 숫자로 관리하기 위해 만들어놨다.

material_pay는 각 재료를 만드는데 최소비용을 저장시켜놓은 리스트이다.

그러면 위상정렬을 어떻게 시작하면 되면

최초에 주어진 재료 N개를 queue에 넣어준다.

그리고 그 queue에서 하나씩 꺼내서

graph[name_idx]를 통해

이 재료로 만들 수 있는 레시피들에서 이 재료를 삭제시켜주었다.

이때 나중에 또 방문할 수 있으니, 있는지 확인을 하고 제거를 해준다.

그리고 이 recipe_order에 있는 set이 전부 사라져서 길이가 0 이면,

그때 queue에 들어갈수 있는지 확인해준다.

우리가 저장해놓은 recipe_dict을 이용해서 현재 재료들의 최저가로 만들었을때 나오는 비용을 계산한다.

비용을 계산한 후,  material_pay에 있는 값과 비교를 해서

최저가가 갱신이 되면 queue에 넣어준다.

그리고 이 반복문은 queue가 빌때까지 무한 반복해준다.

그러면 우리는 결과를 출력할때 두가지로 먼저 나눈다.

레시피와 재료에 아예 LOVE가 없을때, 그때는 -1을 출력해준다.

레시피와 재료에 있지만, 초기값인 float('inf')일때에는 -1을 출력해준다.

왜냐하면 어디선가 재료가 부족해서 LOVE에 아예 접근을 못한상태이기 때문이다.

그리고 1000만이 넘었을때에는 1000만1 그 외에는 재료값을 출력하게 해준다.

푼 사람들 코드 중에 제가 푼 코드보다 가독성이 좋고, 좋은 코드들이 있다.

가독성을 늘리는 방법은 중간에 제가했던 사전작업과 위상정렬을 동시에 해버리면된다.

어떤 상황에서 큐에 들어가는지와 어떤상황에서 종료를 해야하는지 파악하면 풀 수 있는 문제이다.

즉 들어온 입력들 전체를 while문을 돌리면서

단 한번도 최저값이 갱신된적이 없거나, 새로운 재료가 생기지 않았다면, 종료를 해주면 된다.

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

def bfs(red,blue):
    stack = deque()

    stack.append((*red,*blue,0))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while stack:
        rx,ry,bx,by,dis = stack.popleft()

        for i in range(4):
            nrx,nry = rx,ry
            r_p = 0
            while 0<=nrx<N and 0<=nry<M and arr[nrx][nry] != '#' and arr[nrx][nry] != 'O':
                nrx += dx[i]
                nry += dy[i]
                r_p += 1
            nbx,nby = bx,by
            b_p = 0
            while 0<=nbx<N and 0<=nby<M and arr[nbx][nby] != '#' and arr[nbx][nby] != 'O':
                nbx += dx[i]
                nby += dy[i]
                b_p += 1

            if (nbx,nby) == (nrx,nry):
                if arr[nbx][nby] == 'O':
                    continue
                if r_p > b_p:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            elif arr[nbx][nby] == 'O':
                continue
            elif arr[nrx][nry] == 'O':
                return dis+1
            nrx -= dx[i]
            nry -= dy[i]
            nbx -= dx[i]
            nby -= dy[i]
            if not visited[nrx][nry][nbx][nby]:continue
            visited[nrx][nry][nbx][nby] = False
            stack.append((nrx,nry,nbx,nby,dis+1))
    return -1

N,M = map(int,input().split())


arr = []
blue = []
red = []
for x in range(N):
    temp = list(input())
    for y in range(M):
        if temp[y] == 'B':
            blue = (x,y)
        elif temp[y] == 'R':
            red = (x,y)
    arr.append(temp)


visited = [[[[True for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]


result = bfs(red,blue)
print(result)

구슬 탈출의 마지막 시리즈다.

구슬탈출3에서 썼던 코드에서 경로추적이랑 10이상일때 종료인것만 제외시켜줬다.

구슬탈출1~4까지는 다 똑같은 코드이므로,

하나만 잘 풀어놓으면

코드를 1~3군데만 고쳐도 전부 통과할수 있다.

import sys
import heapq

from collections import defaultdict
input = sys.stdin.readline
class Algorithm():
    def __init__(self,num):
        self.num = num
        self.min_heap = []
        self.max_heap = []
    def insert(self,pb_num,diff):
        heapq.heappush(self.min_heap,(diff,pb_num))
        heapq.heappush(self.max_heap,(-diff,-pb_num))
    def find_heap(self,flag):
        result = []
        if flag > 0:
            if self.max_heap:
                while (-self.max_heap[0][1] not in number_set) or number_algo[-self.max_heap[0][1]][0] != self.num or number_algo[-self.max_heap[0][1]][1] != -self.max_heap[0][0]:
                    heapq.heappop(self.max_heap)
                    if not self.max_heap:
                        break
            if self.max_heap:
                result = [-self.max_heap[0][0],-self.max_heap[0][1]]
        else:
            if self.min_heap:
                while (self.min_heap[0][1] not in number_set) or number_algo[self.min_heap[0][1]][0] != self.num or number_algo[self.min_heap[0][1]][1] != self.min_heap[0][0]:
                    heapq.heappop(self.min_heap)
                    if not self.min_heap:
                        break
            if self.min_heap:
                result = self.min_heap[0]
        return result


class Difficulty():
    def __init__(self,num):
        self.num = num
        self.min_heap = []
        self.max_heap = []

    def insert(self,pb_num):
        heapq.heappush(self.min_heap,pb_num)
        heapq.heappush(self.max_heap,-pb_num)
    def find_heap(self,x):
        result = []
        if x > 0:
            if self.min_heap:
                while self.min_heap[0] not in number_set or (number_algo[self.min_heap[0]][1]) != self.num:
                    heapq.heappop(self.min_heap)
                    if not self.min_heap:
                        break
            if self.min_heap:
                result = self.min_heap[0]

        else:
            if self.max_heap:
                while -self.max_heap[0] not in number_set or (number_algo[-self.max_heap[0]][1]) != self.num:
                    heapq.heappop(self.max_heap)
                    if not self.max_heap:
                        break
            if self.max_heap:
                result = -self.max_heap[0]
        return result


N = int(input())
algo_set = set()
diff_set = set()
algo_dict = {}
diff_dict = {}
number_algo = {}
number_set = set()
for _ in range(N):
    number,dif,algo = map(int,input().split())
    if algo not in algo_set:
        algo_dict[algo] = Algorithm(algo)
        algo_set.add(algo)
    if dif not in diff_set:
        diff_dict[dif] = Difficulty(dif)
        diff_set.add(dif)
    algo_dict[algo].insert(number,dif)
    diff_dict[dif].insert(number)
    number_algo[number] = [algo,dif]
    number_set.add(number)


M = int(input())

for i in range(M):
    command,*arg = input().split()
    if command == 'recommend':
        G,x = map(int,arg)
        print(algo_dict[G].find_heap(x)[1])
    elif command == 'recommend2':
        x = int(arg[0])
        diff_check = 0 if x == 1 else float('inf')
        pb_num_check = -1
        for algo_num in algo_dict:
            ch = algo_dict[algo_num].find_heap(x)
            if not ch: continue
            if x == 1:
                if ch[0] >diff_check:
                    diff_check = ch[0]
                    pb_num_check = ch[1]
                elif ch[0] == diff_check:
                    if pb_num_check < ch[1]:
                        pb_num_check = ch[1]
            else:
                if ch[0] < diff_check:
                    diff_check = ch[0]
                    pb_num_check = ch[1]
                elif ch[0] == diff_check:
                    if pb_num_check > ch[1]:
                        pb_num_check = ch[1]
        print(pb_num_check)
    elif command == 'recommend3':
        flag,L_num = map(int,arg)
        result = -1
        if flag == -1:
            L_num = L_num + flag
        while 0<=L_num<=100:
            if L_num in diff_set:
                ch = diff_dict[L_num].find_heap(flag)
                if not ch:
                    L_num = L_num + flag
                    continue
                result = ch
                print(ch)
                break
            L_num = L_num + flag
        if result == -1:
            print(-1)

    elif command == 'solved':
        pb_num = int(arg[0])
        number_set.remove(pb_num)
        del number_algo[pb_num]
    else:
        pb_num,diff_num,algo_num = map(int,arg)
        if algo_num not in algo_set:
            algo_dict[algo_num] = Algorithm(algo_num)
            algo_set.add(algo_num)
        if diff_num not in diff_set:
            diff_dict[diff_num] = Difficulty(diff_num)
            diff_set.add(diff_num)
        algo_dict[algo_num].insert(pb_num,diff_num)
        diff_dict[diff_num].insert(pb_num)
        number_algo[pb_num] = [algo_num,diff_num]
        number_set.add(pb_num)

이 문제는 추천 방식이 총 3개이다.

첫번째 추천은 알고리즘 G에서 가장 난이도와 높은것과 낮은것

두번째 추천은 모든 알고리즘에서 가장 난이도가 높은것과 낮은것

세번째 추천은 주어진 난이도에서 가장 가까운 난이도의 문제를 추천이다.

그래서 나는 크게 2가지의 클래스를 만들어주었다.

각 클래스는 각각 max_heap과 min_heap을 만들어주었는데.

이리 한 이유는 세번째 추천과 , 첫번째추천, 두번째 추천이 flag에 따라 동일한 조건일때 반환해야하는 문제의 조건이 달랐기 때문이다.

각각 max_heap과 min_heap, 그리고 알고리즘 클래스는 알고리즘 번호 난이도 클래스는 난이도 번호를 저장시켜주었다.

그러면 추천이 들어올때마다 while문을 도려서 현재, heap에서 사라져야할 문제들에 대해서, 제거를 해주고,

남은 heap일떄 출력을 해주는 방식으로 했다.

그리고 2번째와 3번째는 난이도와 알고리즘 분류는 최대 100이기 때문에 전체탐색을 해주었다.

좀 더 자세하게 설명하면 2번째 추천은 전체 탐색

3번째 추천은 탐색을 하면서, 0과 100을 넘어갔는데도 만족하는 조건을 못 찾으면 -1을 출력하게 해주었다.

min_heap과 max_heap 그리고 남아있는 문제들에 대한 상태관리를 해야하기 때문에 코드가 길고 복잡했다.

import sys
from collections import defaultdict

input = sys.stdin.readline
const_value = 100000
N = int(input())
re1_dict = defaultdict(dict)
re2_dict = defaultdict(dict)
re3_dict = defaultdict(dict)
problem_dict = dict()
for _ in range(N):
    p_num,l_num,g_num = map(int,input().split())
    calc_num = l_num*const_value + p_num-1
    re1_dict[g_num][calc_num] = 1
    re2_dict[calc_num] = 1
    re3_dict[l_num][p_num] = 1
    problem_dict[p_num] = [l_num,g_num]


M = int(input())
for _ in range(M):
    command,*arg = input().split()

    if command == 'recommend':
        g_num,x = map(int,arg)
        if x > 0:
            calc_num = max( re1_dict[g_num].keys())
        else:
            calc_num = min(re1_dict[g_num].keys())
        l_num = calc_num//const_value
        p_num = calc_num%const_value + 1
        print(p_num)
    elif command == 'recommend2':
        x = int(arg[0])
        if x > 0:
            calc_num = max(re2_dict.keys())
        else:
            calc_num = min(re2_dict.keys())
        l_num = calc_num//const_value
        p_num = calc_num%const_value + 1
        print(p_num)
    elif command == 'recommend3':
        x,find_L_num = map(int,arg)
        if x < 0:
            find_L_num = find_L_num + x
        result = -1
        while 0<=find_L_num<=100:
            if re3_dict.get(find_L_num):
                if x>0:
                    result = min(re3_dict[find_L_num].keys())
                else:
                    result = max(re3_dict[find_L_num].keys())
                break
            find_L_num = find_L_num + x
        print(result)
                
    elif command == 'solved':
        p_num = int(arg[0])
        l_num,g_num = problem_dict[p_num]
        calc_num = l_num*100000 + p_num-1
        del re3_dict[l_num][p_num]
        del re2_dict[calc_num]
        del re1_dict[g_num][calc_num]
    else:
        p_num,l_num,g_num = map(int,arg)
        calc_num = l_num*100000 + p_num-1
        re1_dict[g_num][calc_num] = 1
        re2_dict[calc_num] = 1
        re3_dict[l_num][p_num] = 1
        problem_dict[p_num] = [l_num,g_num]

 두번째 방식은 실행 시간을 포기하는 것이다.

실행시간을 포기하고, 딕셔너리를 통해 추천을 해주는 것이다.

그러면 어떻게 해야할것인가 궁금할 것이다.

3번쨰 추천은 문제번호만 상관하면되기때문에 문제번호를 그대로 넣어주면 된다.

하지만 첫번째와 두번째 추천은

문제 난이도가 동일할시 문제번호의 대소를 구분해주어야한다.

문제에서 주어진 문제번호의 범위는 1~100000이다. 그리고 난이도의 범위는 1~100이다.

그러면 

난이도 * 100000 + (문제번호 -1)을 해주면 한 숫자로 이 문제의 정보를 저장할 수 있다고 생각했다.

난이도가 가장 큰 값이기 때문에, 먼저 앞의 난이도를 비교해주고 앞의 2~3자리가 동일하면 나머지 문제번호를

통해 대소관계를 알수 있을거라 생각했다.

그래서 첫번째, 두번째 추천에는 이 계산된 값을 키 값으로하여, 딕셔너리를 만들어주고,

추천이 들어올때마다 min,max를 통해 원하는 값을 추출해주었다.

추출하는 방법도 간단하게 100000으로 나눈 몫이 난이도이고, 나머지에 +1을 해준 것이 문제번호이다.

그리고 solved를 해줄때에도

위의 공식을 이용해서 문제번호와 난이도를 계산해서 그 키 값을 제거해주는 된다.

대신 시간차가 많이 나는 방식이니, 시간을 줄이고 싶으신분은 min_heap과 max_heap을

어차피 통과만 되면 된다는 분들은 후자의 방법을 사용해도 될것이다.

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님의 풀이이다. 기본적인 아이디어는 비슷하다고 볼 수 있다.

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

from datetime import datetime
from collections import defaultdict
import sys
input = sys.stdin.readline

def convert_L(L):
    day,arg = L.split('/')
    day = int(day)
    hour,min = map(int,arg.split(':'))
    total_min = min + hour*60 + day*24*60
    return total_min

N,L,F = list(input().split())
N = int(N)
F = int(F)
L = convert_L(L)
part_manager_dict = defaultdict(dict)

tardy_dict = defaultdict(int)
for _ in range(N):
    total_string = input()
    time_string = total_string[:16]
    time_S = datetime.strptime(time_string,'%Y-%m-%d %H:%M')
    part_name,person = total_string[16:].split()
    if part_manager_dict[person].get(part_name):
        borrowed_time = time_S - part_manager_dict[person][part_name]
        day = borrowed_time.days
        min = borrowed_time.seconds//60
        to_time = day*60*24 + min
        if to_time > L:
            tardy_dict[person] += (to_time-L)*F
        del part_manager_dict[person][part_name]
    else:
        part_manager_dict[person][part_name] = time_S


if len(tardy_dict.keys()):
    key_list = sorted(tardy_dict.keys())

    for key in key_list:
        print(key,int(tardy_dict[key]))

else:
    print(-1)

문제에 주어진 조건대로 빌리시간을 저장해놓고, 반환한 시간에 그 차이를 통해 지각을 하면, 지각을 한 비용을 추가해주면 된다.

여기서 python 유저들이 주의해야할점은 datetime 모듈이나 time 모듈을 쓰면 시간초과가 날 수가 있으니 조심해야하는 것이다.

제일 좋은 방법은 이 문제는 2021년으로 한정짓고 있기 때문에 문자열을 파싱해서 직접계산하는것이 더 빠를 것이다.

근데 파싱하는게 귀찮으므로, 이 풀이는 넘어가겠다.

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

N,M = map(int,input().split())


INF = float('inf')
graph = [[0 if x == y else INF for y in range(N+1)] for x in range(N+1)]

for _ in range(M):
    x,y,pay = map(int,input().split())

    graph[x][y] = min(graph[x][y],pay)




for mid in range(1,N+1):
    for end in range(1,N+1):
        for start in range(1,N+1):
            if graph[start][end] > graph[start][mid] + graph[mid][end]:
                graph[start][end] = graph[start][mid] + graph[mid][end]

K = int(input())
friend_list = list(map(int,input().split()))
min_value = INF
min_list = []
for city in range(1,N+1):
    temp_max = 0
    for p_num in friend_list:
        if graph[p_num][city] + graph[city][p_num] > temp_max:
            temp_max = graph[p_num][city] + graph[city][p_num]

    if temp_max < min_value:
        min_value = temp_max
        min_list = [city]
    elif temp_max == min_value:
        min_list.append(city)

print(*min_list)

 이 문제는 플로이드와샬을 이용해 모든 경로에 대해 이동비용을 먼저 계산을 해준다.

그리고 전체 도시들을 for문을 돌리면서, 친구들의 이동비용을 구하고,

각 친구들의 이동비용의 최대값의 최소가 되는 경우를 구해서 출력해주면 된다.