Coding 공부

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문을 돌리면서, 친구들의 이동비용을 구하고,

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

import sys
input = sys.stdin.readline

N = int(input())


problem_dict = {}
re1_dict = {}

for _ in range(N):
    pb_num,l_num = map(int,input().split())
    re1_dict[(l_num,pb_num)] = 1
    problem_dict[pb_num] = l_num


M = int(input())

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

    if command == 'add':
        pb_num,l_num = map(int,arg)
        problem_dict[pb_num] = l_num
        re1_dict[(l_num,pb_num)] = 1
    elif command == 'recommend':
        flag = int(arg[0])
        if flag > 0:
            keys = max(re1_dict.keys())
        else:
            keys = min(re1_dict.keys())
        print(keys[1])
    else:
        pb_num = int(arg[0])
        l_num = problem_dict[pb_num]
        del problem_dict[pb_num]
        del re1_dict[(l_num,pb_num)]

 이 문제를 풀때 사실 boj.kr/21944 번을 먼저 풀었기 때문에 그 때 시도했던 후자 방식을 먼저 적용시켜보았다.

제한 시간내에 동작은 하지만 위 풀이는 추천하지 않는다.

문제를 푸는 아이디어는 다음과 같다. 어차피 우리는 recommend를 해야하고, 그때의 값들을 관리하는 것이다.

그러면 이 문제를 풀때 dictinory를 이용하기로 했다.

(난이도, 문제번호)를 key 값으로 하는 dictionary를 만들어준 뒤 

recommend를 해줄때 1일때에는 최대값

-1일때는 최소값을 구해서 출력해주는 식으로 했다.

max,min이 알아서 앞에서부터 비교를 해주니 가능한 방식이다.

그리고 문제를 풀었을 때에는

problem_dict 이라는 dictionary에 문제번호와 난이도를 매핑시켜준 딕셔너리가 있다.

그러면 problem_dict에서 solved 된 문제번호를 통해 난이도를 가져오고,

re1_dict의 값을 제거해주면 된다.

import sys
import heapq
input = sys.stdin.readline

def recommend(flag,heap):
    flag = -flag
    while heap and (heap[0][1]*flag not in problem_dict.keys() or problem_dict[heap[0][1]*flag] != heap[0][0]*flag):
        heapq.heappop(heap)
    result =heap[0]
    result = result[1]*flag
    return result

N = int(input())
max_heap = []
min_heap = []
problem_dict = {}
for _ in range(N):
    pb_num,l_num = map(int,input().split())
    max_heap.append((-l_num,-pb_num))
    min_heap.append((l_num,pb_num))

    problem_dict[pb_num] = l_num
heapq.heapify(max_heap)
heapq.heapify(min_heap)
M = int(input())

for _ in range(M):
    command,*arg = input().split()
    if command == 'add':
        pb_num,l_num = map(int,arg)
        heapq.heappush(max_heap,(-l_num,-pb_num))
        heapq.heappush(min_heap,(l_num,pb_num))
        problem_dict[pb_num] = l_num
    elif command == 'solved':
        pb_num = int(arg[0])
        del problem_dict[pb_num]
    else:
        flag = int(arg[0])
        if flag > 0:
            print(recommend(flag,max_heap))
        else:
            print(recommend(flag,min_heap))

이게 정석적인 풀이이다.

min_heap 과 max_heap을 이용해서 풀었다.

여기서 주의해야할점은 problem_dict을 활용해 사라진 문제들을 찾아서, 제거를 해주어야한다.

while문을 통해 없는 문제들은 전부 없애주고, while문을 탈출했을때 heap[0]에 있는 값을 return 해주면 된다.

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

def bfs(x,y):

    queue = deque()
    queue.append((x,y))
    visited[x][y] = False
    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if visited[nx][ny] and arr[nx][ny] >= T:
                    visited[nx][ny] = False
                    queue.append((nx,ny))


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

arr = []

for x in range(N):
    input_list = list(map(int,input().split()))
    temp = []
    for k in range(M):
        temp.append(sum(input_list[3*k:3*(k+1)]))

    arr.append(temp)

T = int(input())

T = 3*T


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

dx = [-1,1,0,0]
dy = [0,0,-1,1]

cnt = 0
for x in range(N):
    for y in range(M):
        if arr[x][y] >= T  and visited[x][y]:
            bfs(x,y)
            cnt += 1

print(cnt)

이 문제는 처음들어올때부터 값을 계산해주는 방식으로 했다.

이 문제를 평균값을 구하면 float 값이 나올것 같아서, 어차피 문제에서 경계값이 정수이고,

한 픽셀을 구성하는 것은 3개로 고정적이므로 처음에 들어올때 열을 기준으로 3개씩 짤라주면서 그때의 합을 전부 저장하는 방식으로 했다.

이렇게 변형햔 배열을 가지고 BFS를 하면 되는데

계산의 편의성을 위해 경계값이 들어오자마자 그냥 3배를 해주었다.

그리고 난뒤에는 일반적인 BFS,DFS를 해주면 되는 문제이다.

방문을 하지않고, 경계값을 넘는 위치에 대해 bfs를 해서 인접한 픽셀들을 구하고, 함수가 끝난뒤에 개수를 늘려주었다.

import sys
input = sys.stdin.readline
N,M = map(int,input().split())

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


start = int(input())
stack = [start]
cnt = 0
visited = [True for _ in range(N+1)]
visited[start] = False
while stack:
    x = stack.pop()

    for next_node in graph[x]:
        if visited[next_node]:
            visited[next_node] = False
            cnt += 1
            stack.append(next_node)

print(cnt)

주어진 작업을 시행하기위해서 필요한 작업의 양을 구하는 방법은

처음에 들어온 입력을 자식노드에 부모노드를 기억해놓고,

주어진 노드에서부터, 부모로 가면서 부모의 수를 세어주면 된다.

import sys
input = sys.stdin.readline
def dfs(node):
    global result 
    if not len(graph[node]):
        ball_cnt_list[parent_list[node]] += (ball_cnt_list[node] -1)
        result += abs(ball_cnt_list[node] - 1)
    else:
        for next_node in graph[node]:
            dfs(next_node) 
        if parent_list[node] != -1:
            ball_cnt_list[parent_list[node]] += ball_cnt_list[node] - 1
            result += abs(ball_cnt_list[node] - 1)



while True:
    N = int(input())

    if N == 0:
        break
    graph = [[] for _ in range(N+1)]
    parent_list = [-1 for _ in range(N+1)]
    ball_cnt_list = [0 for _ in range(N+1)]
    indegree = [0 for _ in range(N+1)]
    for _ in range(N):
        node_num,ball_cnt,*arg = map(int,input().split())
        if arg[0]>0:
            for child_node in arg[1:]:
                graph[node_num].append(child_node)
                parent_list[child_node] = node_num
                indegree[child_node] += 1
        ball_cnt_list[node_num] = ball_cnt

    result = 0
    for k in range(1,N+1):
        if indegree[k] == 0:
            dfs(k)
    print(result)

 이 문제를 해결하는데 어려움을 겪었다.

이 문제를 해결하는 방식은 가장 끝 리프노드부터 1씩 무조건 맞춰주는 것이다.

그리고 그때의 절대값들을 전부 더해주는 방식을 해주면 된다.

현재 노드에서 1와의 차이를 부모노드로 옮겨주고,

그때 차이의 절대값을 결과에 계속 더해주면 된다.

# dotorya님 풀이

import sys
input = sys.stdin.readline
def dfs(node):
    global result 
    cnt = ball_cnt_list[node] -1

    for next_node in graph[node]:
        cnt += dfs(next_node)

    result += abs(cnt)
    return cnt



while True:
    N = int(input())

    if N == 0:
        break
    graph = [[] for _ in range(N+1)]
    ball_cnt_list = [0 for _ in range(N+1)]
    indegree = [0 for _ in range(N+1)]
    for _ in range(N):
        node_num,ball_cnt,*arg = map(int,input().split())
        if arg[0]>0:
            for child_node in arg[1:]:
                graph[node_num].append(child_node)
                indegree[child_node] += 1
        ball_cnt_list[node_num] = ball_cnt

    result = 0
    for k in range(1,N+1):
        if indegree[k] == 0:
            dfs(k)
    print(result)

두 번째 풀이는 dotorya님 풀이를 복기한 것이다.

끝노드부터 하는 것은 동일하다.

그리고 현재의 격차를 상위노드로 전달해주고, 결과에는 그 절대값을 계속 누적해서 더해주면 되는 것이다.