import sys
def input():
return sys.stdin.readline().rstrip()
T = int(input())
dp = [i for i in range(101)]
for i in range(100):
for coin in [10,25]:
if i +coin > 100:continue
dp[i+coin] = min(dp[i+coin],dp[i]+1)
for _ in range(T):
N = int(input())
answer = 0
while N>0:
answer += dp[N%100]
N//=100
print(answer)
이 문제는 100까지의 최소 코인의 개수를 구해준 뒤에, 100단위로 나눠주면서 그 개수를 더해주면 된다.
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 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로 푸는 방식말고도 그리디방식으로도 푸는 방식이 있다하지만, 배움이 부족해,
그래서, 최초로 실행되는 위치이후로는 작업이 끝날때까지 매번 실행이 될것이기 때문에, 최초의 순증가 수열의 위치가
중요합니다.
그래서 여기서 구해야할것은 최초 프로세스가 실행되는 순증가수열의 최초의 위치,
그리고 프로세스가 마지막으로 실행되는 순증가수열의 마지막 위치, 이 두가지가 중요합니다.
만약 마지막 순증가수열의 프로세스 위치를 E 그리고 최초의 순증가 수열의 최초의 위치가 S라 하면
작업시간은 E - S + 1이 된다. 그리고 이 문제의 최대시간은 10^5이므로, 최대 priority 는 10^5+1로 설정을 하고,
그 최대값에서 최대 priority - S를 해주면 된다.
# jthis님 풀이
import sys
input = sys.stdin.readline
N = int(input())
process_state = [[0 for _ in range(2)] for _ in range(1000001)]
# 0번 인덱스 총 시간
# 1번 인덱스 우선순위
arr = list(map(int,input().split()))
total_process = 0
for i in range(N):
cur_process = arr[i]
if not process_state[cur_process][0]:
total_process += 1
process_state[cur_process][0] += 1
pre_priority = 1
last_value = arr[-1]
process_state[last_value][1] = 1
for i in range(N-2,-1,-1):
cur_process = arr[i]
if not process_state[cur_process][1]:
# 처음 나왔을때
if cur_process<last_value:
process_state[cur_process][1] = pre_priority
# 이후의 값보다 낮은 값이면, 같은 순증가이므로, 같은 우선순위
else:
process_state[cur_process][1] = pre_priority + 1
else:
process_state[cur_process][1] += 1
pre_priority = process_state[cur_process][1]
last_value = cur_process
sys.stdout.write(str(total_process)+'\n')
for i in range(1000001):
if process_state[i][0]:
sys.stdout.write(str(i)+' '+str(process_state[i][0])+' '+str(process_state[i][1])+'\n')
이 방식은 앞선 방식과 뒤에서부터 찾아가는 방식이다.
먼저 전체 실행시간은 반복문을 돌리면서 총 시간을 더해준다.
그리고 이 문제에서 쓰는 프로세스의 종류는 total_process를 통해 구해준다.
이 문제도 같은 순증가 수열에 있는건지 확인을 해주는 방식이다.
이 문제의 우선순위가 낮은것부터 제일 뒤에서부터 실행되는 것을 응용한 것이다.
가장 마지막에 실행되는 것은 일단 가장 우선순위가 낮은 1일 것이다.
그리고 그때의 process_id보다 그이전의 process_id가 낮다는 것은 같은 순증가수열에 있고,
같은 우선순위 그룹에 잇는 것임을 알 수 있다. 그러므로 최초의 우선순위를 같게 설정을 해주면 된다.
그런데 만약 이전 process_id가 더 크거나 같으면, 다른 순증가 수열에 있는 것이므로,
현재 우선순위보다 1을 높여줘야한다.
그리고 최초로 만난 프로세스가 아니라면, 이미 자기의 초기 우선순위를 알고 있으므로, 1씩 증가시켜 주면 된다.
