Coding 공부

import sys
 
def input():
    return sys.stdin.readline()
 
N = int(input())
INF = float('inf')
dp = [INF for _ in range(101)]
dp[2] = 1
dp[3] = 7
dp[4] = 4
dp[5] = 2
dp[6] = 6
dp[7] = 8
dp[8] = 10
 
for num in range(9,101):
    for i in range(2,8):
        if i != 6:
            dp[num] = min(dp[num],dp[num-i]*10+dp[i])
        else:
            dp[num] = min(dp[num],dp[num-i]*10)
for _ in range(N):
    k = int(input())
    
    max_value = ('7' if k%2 else '1' ) +'1'*(k//2-1)
    print(dp[k],max_value)

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

2개부터 8개까지의 성냥개비를 이용해서 만들 수 있는 최소의 수가 있다.

먼저 이 수들을 각각 저장을 해주는 것이다.

단 여기서 주의해야할 점은 성냥개비의 개수가 6개일때다.

6개일때는 원래 최저의 수는 0이지만, 자리수가 1개일때 0이 올수가 없다. 이 점만 주의해주면 된다.

이렇게 2~8개의 최소 숫자를 구해주고

9개부터는 그리디하게 찾아주면 된다.

dp [ 현재 성냥의 개수 - i개 ] *10 + dp[i] 와 dp[현재 성냥의 개수] 의 최소값을 비교해서 갱신해주면 된다.

그리고 위에 말했듯이 6개일때는 가장 작은 수는 0 이므로 *10만 해주면 된다.

이렇게 최소 숫자를 구했으면,

최대 숫자를 구해야한다.

여기서 가장 큰 숫자를 만드는 법은 가장 적은 개수로 만들수 있는 1로 채우는 것이다.

그런데 이럴때 문제는 성냥의 개수가 홀수일때 문제가 된다.

성냥의 개수가 홀 수 일때 1개가 남아서, 어떠한 숫자도 만들수 없다.

그러므로 주어진 성냥개비의 숫자가 홀수이면, 가장 앞의 수를 1이 아닌 성냥개비 3개로 만들수 있는 가장 큰수를 만들어줘야한다.

그에 부합하는 숫자는 7 이므로,

주어진 성냥 개비의 숫자가 홀수이면 7 아니면 1을 붙이고, 성냥개비를 2로 나눈 몫에서 1을 뺀숫자만큼 붙여주면 된다.

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단위로 나눠주면서 그 개수를 더해주면 된다.

왜냐하면

이 문제에서 쓰이는 동전은 [1,10,25]로 되어있고

각 100^k 만 곱해진 동전이기 때문이다.

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로 푸는 방식말고도 그리디방식으로도 푸는 방식이 있다하지만, 배움이 부족해,

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

N = int(input())
 
arr = list(map(int,input().split()))
 
arr.sort()
min_value = 0
if len(arr)%2:
    min_value = arr.pop()
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
else:
    lens = len(arr)//2
    for _ in range(lens):
        t = arr.pop() + arr.pop(0)
        min_value = max(min_value,t)
print(min_value)

정렬을 해주고, 가장 첫번째값과 가장끈값을 더한값의 최소값을 출력해주면 된다.

N,K = map(int,input().split())
N += 1
N_list = list(str(N))
cur_idx = -1
max_idx = len(N_list)
while True:
    if N_list.count('5') >= K:
        break
    while N_list[cur_idx] == '5' and abs(cur_idx) < max_idx:
        cur_idx -= 1
    
    cur_value = int(''.join(N_list))
    cur_value = cur_value + 10**(abs(cur_idx)-1)
    N_list = list(str(cur_value))
    max_idx = len(N_list)
 
 
 
print(''.join(N_list))

이 문제는 간단하다. 가장 뒤에서부터 5를 만들어주면 되는것이다. 

여기서 주의해야할 점은 다음과 같은 경우이다. K가 1이고, 주어진 N이 48이였을때

우리는 49부터 탐색을 시작하게 되는데, 그때 50이 되면 K를 만족하는 수가 된다.

그러므로 우리는 5가 아닌 자리수부터 1씩 늘려가면서, 가장 오른쪽 자리부터 5를 만들어줘야한다.

그래서 나는 cur_idx 라는것을 뒤에서부터 접근하기 위해 -1로 해주었고, 

abs(cur_idx) - 1을 해주면 해당 자릿수를 구할 수 있다. 즉 첫번째 자리는 1이 더해지게, 오른쪽에서 두번째자리는 10,

세번째 자리는 100이 더해지게 만들어주는 것이다.

이럴때 주의해야할 점은 999일때이다. 999에서 1을 더해주면 1000이된다. 그러면 우리의 idx가 넘어가게 되므로,

max_idx를 새로 계속 갱신을 해주었다.

그리고 555 이고, 구하는 K가 4일때를 대비해서 while문에 abs(cur_idx)<max_idx 를 넘어갈때를 escape 해주었다.

이런식으로 오른쪽 자리수부터 1씩 더해가면서 5를 만들어주고, 그리고 count를 해서 넘어가면

반복문을 빠져 나올 수 있게 해주었다.

여담으로 문제 제목이 직관적이고, 가장 짧은 문제였던 것 같다.

import sys
 
input = sys.stdin.readline
N = 1000001
max_priority = N//10
T = int(input())
INF = float('inf')
start_process_time = [INF]*N
end_process_time = [0]*N
arr = list(map(int,input().split()))
mono_times = 1
prev_process = -1
for i in range(T):
    cur_process = arr[i]
    if prev_process >= cur_process:
        mono_times += 1
 
    start_process_time[cur_process] = min(start_process_time[cur_process],mono_times)
    end_process_time[cur_process] = max(end_process_time[cur_process],mono_times)
    prev_process = cur_process
 
 
active_process_list = []
for i in range(N):
    if end_process_time[i]:
        active_process_list.append(i)
 
 
 
result = []
for process_id in active_process_list:
    priority = max_priority-1-start_process_time[process_id]
    spend_time = end_process_time[process_id]-start_process_time[process_id] + 1
    result.append((str(process_id),str(spend_time),str(priority)))
 
 
sys.stdout.write(str(len(active_process_list))+'\n')
 
 
for i in range(len(active_process_list)):
    sys.stdout.write(' '.join(result[i])+'\n')

이 문제 부터는 사실상 저 혼자만의 힘으로 푼 것이 아닌, 코딩개(chogahui05)님의 해설을 보고,

푼 것이기 때문에 온전한 실력이라고 할수 없고, 정확한 설명은 아래 링크를 참조하시길 바랍니다.

https://github.com/cdog-gh/gh_coding_test

이 문제는 가희배 3번 문제 boj.kr/21773 의 연장선상이라고 보면 됩니다.

여기서는 실행된 프로세스 목록을 보고 프로세스의 우선순위와 실행시간을 구하는 문제입니다.

위의 설명에서도 잘 나와있듯이, 이 문제는 순증가수열별로 나누면 됩니다.

왜냐하면, 이 문제에서 먼저 같은 우선순위이면, 무조건 id가 적은것부터 나오게 됩니다.

그러므로 순증가수열 내에 있는 id들은 같은 우선순위로 시작하는 것을 알 수 있습니다.

그래서, 최초로 실행되는 위치이후로는 작업이 끝날때까지 매번 실행이 될것이기 때문에, 최초의 순증가 수열의 위치가

중요합니다.

그래서 여기서 구해야할것은 최초 프로세스가 실행되는 순증가수열의 최초의 위치,

그리고 프로세스가 마지막으로 실행되는 순증가수열의 마지막 위치, 이 두가지가 중요합니다.

만약 마지막 순증가수열의 프로세스 위치를 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씩 증가시켜 주면 된다.

이 문제는 프로세스의 수행시간이 어떻게 되는지, 우선순위가 어떻게 구성되는지에 대해서

알아야 풀 수 있는 문제인것같다.

numbers = [0]*500001
N = int(input())
arr = map(int,input().split())
for k in arr:
    numbers[k] += 1
print(max(numbers))