1932 정수 삼각형

처음에는 엄청 쉬운 문제인 줄 알고 풀었다가 내가 문제를 잘못 이해한 것이였다
좀 헤메다가 금방 다시 알고리즘을 떠올렸다
그 동안 알고리즘 문제를 풀었던 것이 도움이 된 것 같다

알고리즘
위 층에서 큰 값을 골라 매번 값을 누적하여 갱신해준다.
그러면 최종적으로 맨 아래 층은 항상 제일 큰 값만을 선택했을 경우의 값으로 갱신된다.
그러므로 맨 아래층에서 제일 큰 값을 print

import sys
input = sys.stdin.readline

N = int(input())
map_list = [ 0 for _ in range(N) ]

# 2차원 리스트에 입력 값을 모두 담는다
for _ in range(N):
    map_list[_] = list(map(int, input().split()))



if N==1:
    print(map_list[0][0])
else:
    for i in range(1,N):
        for j in range(i+1):
            #젤 왼쪽 값과 젤 오른쪽 값은 고려해야 할 값이 하나이다.
            if j == 0:
                map_list[i][j] += map_list[i-1][j]
            elif j == i:
                map_list[i][j] += map_list[i-1][j-1]
            #고려해야 할 값이 두 값이므로 둘 중 큰 값을 선택하여 갱신
            else:
                map_list[i][j] += max(map_list[i-1][j-1],map_list[i-1][j])
    print(max(map_list[N-1]))

14501 퇴사

n = int(input())

t_list = []
p_list = []
answer = [0] * (n + 1)

for i in range(n):
    t, p = map(int, input().split())
    t_list.append(t)
    p_list.append(p)

for i in range(n - 1, -1, -1):
    if t_list[i] + i > n:
        answer[i] = answer[i + 1]
    else:
        answer[i] = max(p_list[i] + answer[i + t_list[i]], answer[i + 1])
        
print(answer[0])

2778 행성 터널

• 모든 좌표들의 x값, y값, z값을 각각 별도로 정렬한 후 각 축에서 바로 옆에 있는 좌표와의 거리만 edge들을 고려
• Union-Find 방식을 사용해 크루스칼 알고리즘을 이용하여 풀이

import sys
input = sys.stdin.readline

def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n = int(input())
parent = list(range(n))
x = []
y = []
z = []

for i in range(n):
    a, b, c = map(int, input().split())
    x.append((a, i))
    y.append((b, i))
    z.append((c, i))
x.sort()
y.sort()
z.sort()
edges = []
for i in range(n - 1):
    edges.append((x[i + 1][0] - x[i][0], x[i][1], x[i + 1][1]))
    edges.append((y[i + 1][0] - y[i][0], y[i][1], y[i + 1][1]))
    edges.append((z[i + 1][0] - z[i][0], z[i][1], z[i + 1][1]))

edges.sort()
answer = 0

for e in edges:
    cost, a, b = e
    if find_parent(a) != find_parent(b):
        union_parent(a, b)
        answer += cost
print(answer)