2019.03.21) 소프트웨어 마에스트로 마지막 스퍼트 2편(dp, 삼분탐색) - 1766, 2169, 2504, 2512, 8986 (PyPy3)

위상정렬 복습이랑 삼분탐색까지 익혔다

1766번

N, M = map(int, input().split())
 
graph = {i: list() for i in range(1, N + 1)}
count = {i: 0 for i in range(1, N + 1)}
 
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    count[b] += 1
 
queue = list()
for i in range(1, N + 1):
    if count[i] == 0:
        queue.append(i)
 
result = ''
for _ in range(N):
    queue.sort()
    now = queue.pop(0)
    result += str(now) + ' '
    for nxt in graph[now]:
        count[nxt] -= 1
        if count[nxt] == 0:
            queue.append(nxt)
 
print(result)

2169번

N, M = map(int, input().split())
 
dp = list()
ma = list()
 
dp.append([0 for i in range(M)])
 
for _ in range(N):
    ma.append(list(map(int, input().split())))
 
 
dp = list()
 
tmp = [ma[0][0]]
for i in range(M - 1):
    tmp.append(tmp[i] + ma[0][i + 1])
 
dp.append(tmp)
 
for i in range(1, N):
    tmp = [dp[i - 1][j] + ma[i][j] for j in range(M)]
    tmp1 = [tmp[0]]
    for j in range(M - 1):
        tmp1.append(max(tmp1[j] + ma[i][j + 1], tmp[j + 1]))
    tmp2 = [0] * (M - 1) + [tmp[-1]]
    for j in range(M - 1, 0, -1):
        tmp2[j - 1] = max(tmp2[j] + ma[i][j - 1], tmp[j - 1])
    for j in range(M):
        tmp[j] = max(tmp1[j], tmp2[j])
    dp.append(tmp)
 
print(dp[-1][-1])

2504번

st = input()
 
stack = list()
 
 
i = 0
result = 0
tmp_result = 1
f = False
before = ''
while i < len(st):
    if st[i] == '(':
        stack.append(2)
    if st[i] == ')':
        if len(stack) == 0:
            f = True
            break
        s = stack.pop()
 
        if s == 2:
            if before == '(':
                tmp = s
                for z in stack:
                    tmp *= z
 
                result += tmp
        else:
            f = True
            break
 
    if st[i] == '[':
        stack.append(3)
    if st[i] == ']':
        if len(stack) == 0:
            f = True
            break
        s = stack.pop()
 
        if s == 3:
            if before == '[':
                tmp = s
                for z in stack:
                    tmp *= z
 
                result += tmp
        else:
            f = True
            break
    before = st[i]
    i += 1
 
if len(stack) != 0 or f:
    print(0)
else:
    print(result)

2512번

N = int(input())
 
li = list(map(int, input().split()))
 
S = int(input())
 
li.sort()
 
left = 1
 
right = li[-1]
 
re = 0
 
 
while left <= right:
    mid = (left + right) // 2
    tmp = 0
    for i in li:
        if i < mid:
            tmp += i
        else:
            tmp += mid
 
    if tmp <= S:
        re = mid
        left = mid + 1
 
    if tmp > S:
        right = mid - 1
 
print(re)

8986번

N = int(input())
 
li = list(map(int, input().split()))
 
left = 1
 
right = int(1e9)
 
re = int(1e18)
 
while right - left > 2:
    pos1 = (left * 2 + right) // 3
    pos2 = (left + right * 2) // 3
 
    tmp1 = 0
    tmp2 = 0
    for i in range(N):
        tmp1 += abs(li[i] - (li[0] + pos1 * i))
        tmp2 += abs(li[i] - (li[0] + pos2 * i))
    re = min(re, tmp1, tmp2)
    if tmp1 == tmp2:
        left = pos1
        right = pos2
    elif tmp1 > tmp2:
        left = pos1 + 1
    else:
        right = pos2
    # print()
 
print(re)