Jinho Tech

처음에는 아래와 같이 첫날부터 확인하는 방식으로 풀었다. 

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]

for i in range(N):
    for j in range(i + li[i][0], N+1):
        if dp[j] < dp[i] + li[i][1]:
            dp[j] = dp[i] + li[i][1]

print(dp[-1])

통과되긴 해도 일단 반복문이 2개라 아래 사진과 같이 무의미한 동작이 상당히 많다.

반복문 하나로 끝낼 방법이 없을까 하다가 그냥 마지막 날부터 확인하면 되겠다는 생각이 들어 아래와 같이 수정했다.

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]

for i in range(N-1, -1, -1):
    if i + li[i][0] > N:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(dp[i+1], li[i][1] + dp[i + li[i][0]])
    
print(dp[0])

간단한 BFS 문제이다.

S에서 G로 가는 최단경로의 길이를 출력해주면 된다. 경로가 없다면 No Exit 출력

from collections import deque

def bfs(i, j):
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    q = deque()
    q.append((i, j))
    check[i][j] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < C) and graph[Y][X] != 'X' and check[Y][X] == -1:
                check[Y][X] = check[y][x] + 1
                if graph[Y][X] == 'G':
                    return check[Y][X]
                q.append((Y, X))
    return None

for _ in range(int(input())):
    R, C = map(int, input().split())
    graph = [input() for a in range(R)]
    check = [[-1]*C for b in range(R)]
    
    for i in range(R):
        for j in range(C):
            if graph[i][j] == 'S':
                ans = bfs(i, j)
                print(f"Shortest Path: {ans}" if ans else "No Exit")

기본적인 그리디 알고리즘 문제이다. 

for _ in range(int(input())):
    j, N = map(int, input().split())
    li = []
    for i in range(N):
        r, c = map(int, input().split())
        li.append(r*c)
    li.sort(reverse=True)
    cnt = 0
    while j > 0:
        j -= li[cnt]
        cnt += 1
    print(cnt)

기본적인 그래프 탐색 문제이다. 최단거리를 찾는 문제이므로 BFS로 풀었다.

from collections import deque

def bfs():
    q = deque()
    q.append((0))
    while q:
        node = q.popleft()
        n = li[node]
        if check[n] == 0 and node != n:
            q.append(n)
            check[n] = check[node] + 1
            if n == K:
                return ;
    
N, K = map(int, input().split())
li = [int(input()) for _ in range(N)]
check = [0]*N
bfs()
print(check[K] if check[K] else -1)

기본적인 BFS, DFS 문제이다. (N, N) 좌표에 도착할 수 있는지를 확인해주면 된다.

BFS 풀이

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x, li[y][x]))
    while q:
        y, x, d = q.popleft()
        for i, j in [(1, 0), (0, 1)]:
            Y, X = y + d*i, x+ d*j
            if 0 <= Y < N and 0 <= X < N and d != 0:
                if Y == X == N-1:
                    return True
                q.append((Y, X, li[Y][X]))
    return False
        
N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]    
print("HaruHaru" if bfs(0, 0) else "Hing")

DFS 풀이

import sys
sys.setrecursionlimit(10000)

def dfs(y, x):
    global ok
    d = li[y][x]
    for i, j in [(1, 0), (0, 1)]:
        Y, X = y + d*i, x+ d*j
        if 0 <= Y < N and 0 <= X < N and d != 0:
            if Y == X == N-1:
                ok = 1
                return ;
            dfs(Y, X)
        
N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
ok = 0
dfs(0, 0)
print("HaruHaru" if ok else "Hing")

기본적인 그래프 탐색 문제이다. 

각 노드별로 몇 명의 사람을 만날 수 있는지 확인하고, 최댓값의 인덱스를 출력해주면 된다 -> res.index(max(res))

def dfs(node, cnt):
    check[node] = 1
    n = graph[node][0]
    if check[n] == 0:
        cnt = dfs(n, cnt+1)
    return cnt

N = int(input())
graph = [[] for _ in range(N+1)]
res = [0]*(N+1)
for u in range(1, N+1):
    v = int(input())
    graph[u].append(v)
for i in range(1, N+1):
    check = [0]*(N+1)
    res[i] = dfs(i, 1)
print(res.index(max(res)))

브루트포스 알고리즘 & 백트래킹 문제이다.

나누기 처리를 할 때 int(n1 / n2) 또는 -(-n1 / n2) 같은 방식으로 나눠야 하는데,

처음에 이걸 몰라서 계속 틀렸다.

def dfs(res, i, add, sub, mul, div):
    global N
    if i == N:
        res_li.append(res)
    else:
        if add:
            dfs(res + nums[i], i+1, add-1, sub, mul, div)            
        if sub:
            dfs(res - nums[i], i+1, add, sub-1, mul, div)
        if mul:
            dfs(res * nums[i], i+1, add, sub, mul-1, div)
        if div:
            dfs(int(res / nums[i]), i+1, add, sub, mul, div-1)          
    
N = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
res_li = []

dfs(nums[0], 1, add, sub, mul, div)
print(max(res_li))
print(min(res_li))

기본적인 BFS 문제이다. 

B가 200점 이상이 되는 최단경로는 없을 것 같아서 check 리스트 크기를 200으로 정했다. 

from collections import deque

def bfs(S, T):
    q = deque()
    q.append((S, T, 0))
    check = [-1]*(200)
    while q:
        node, t, c = q.popleft()
        if node <= t and check[node] == -1:
            q.append((node*2, t+3, c+1))
            q.append((node+1, t, c+1))
            if node == t:
                return c

C = int(input())
for _ in range(C):
    S, T = map(int, input().split())
    print(bfs(S, T))

앞, 뒤 방향과 노드별 이동거리 모두 고려해줘야 되는 bfs 문제이다.

아래와 같이 앞, 뒤 방향의 경우로 둘로 나눠서 반복문을 짜면 96ms로 통과된다.

from collections import deque

def bfs(a, b, bridge, N):
    q = deque()
    q.append(a-1)
    check = [-1]*N
    check[a-1] = 0
    while q:
        node = q.popleft()
        for n in range(node, N, bridge[node]):
            if check[n] == -1:
                q.append(n)
                check[n] = check[node] + 1
                if n == b-1:
                    return check[n]
        for n in range(node, -1, -bridge[node]):
            if check[n] == -1:
                q.append(n)
                check[n] = check[node] + 1
                if n == b-1:
                    return check[n]
    return -1

N = int(input())
bridge = list(map(int, input().split()))
a, b = map(int, input().split())
print(bfs(a, b, bridge, N))

단순하게 짧게 짜 봤는데도 976ms로 통과됐다.

from collections import deque

def bfs(a, b, bridge, N):
    q = deque()
    q.append(a-1)
    check = [-1]*N
    check[a-1] = 0
    while q:
        node = q.popleft()
        for n in range(N):
            if (n-node)%bridge[node] == 0 and check[n] == -1:
                q.append(n)
                check[n] = check[node] + 1
                if n == b-1:
                    return check[n]
    return -1

N = int(input())
bridge = list(map(int, input().split()))
a, b = map(int, input().split())
print(bfs(a, b, bridge, N))

단순 문자열 & 구현 문제이다.

N = int(input())
S = input()
res = ''
for c in S:
    if c not in "JAVA":
        res += c
print(res if res else "nojava")

단순 구현 문제이다.

max_score = [100, 100, 200, 200, 300, 300, 400, 400, 500]
score = list(map(int, input().split()))
total_score, hacker = 0, 0
for i in range(9):
    if score[i] > max_score[i]:
        hacker = 1
    total_score += score[i]
if hacker:
    print("hacker")
else:
    print("draw" if total_score >= 100 else "none")

단순한 백트래킹 문제이다.

def dfs(depth):
    if depth == 6:
        print(*li)
        return ;
    for i in range(n):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        for j in range(i+1, n):
            check[j] = 0
        
while 1:
    t = list(map(int, input().split()))
    n, nums = t[0], t[1:]
    if n == 0:
        break
    li = []
    check = [0]*n
    dfs(0)
    print()

골드 3 난이도 치고는 쉬운 다익스트라 알고리즘 문제이다.

N-1개(1->X->1, 2->X->2, ..., N->X->X (X->X->X 제외))의 최단경로 중 최댓값을 출력해주면 된다.

import heapq
import sys
INF = sys.maxsize
# input = sys.stdin.readline

def dijkstra(start, end):
    q = []
    heapq.heappush(q, (0, start))
    dis = [INF]*(N+1)
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))
    return dis[end]
    
N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
t = 0
for i in range(1, N+1):
    if i == X:
        continue
    t = max(t, dijkstra(i, X) + dijkstra(X, i))
print(t)

기본적인 우선순위 큐 문제이다. 이 문제도 골드 4 난이도 치고는 쉽다.

우선순위 큐에 남은 수가 2개 이하가 되기 전까지 제일 작은 두 값을 pop 해서 더하고,

그 합을 우선순위 큐에 추가하고 res에 더해주면 된다. 마지막에 res를 출력해주면 끝

import heapq
import sys
input = sys.stdin.readline

N = int(input())
q = []
for _ in range(N):
    n = int(input())
    heapq.heappush(q, n)
if N == 1:
    print(0)
else:
    res = 0
    while len(q) > 1:
        t = heapq.heappop(q)+heapq.heappop(q)
        res += t
        heapq.heappush(q, t)
    print(res)

골드 5 난이도 치고는 매우 쉬운 우선순위 큐 문제이다.

최대 힙 우선순위 큐로 구현해서 N번째 pop결과를 출력해주는 식으로 풀어도 답은 맞지만 메모리 초과가 뜬다.

heapq의 nlargest를 사용해서 해결했다 -> q값 중 제일 큰 N개의 값을 추출

import heapq

N = int(input())
q = []
for _ in range(N):
    for n in map(int, input().split()):
        heapq.heappush(q, n)
    q = heapq.nlargest(N, q)
heapq.heapify(q)
print(heapq.heappop(q))