2월 3주차 코딩 테스트

목차

1. 금쪽이 상담소
2. 삽질의 대가
3. 한 번의 거짓말
4. 제한된 비행편
5. 전광판 컨트롤

1. 금쪽이 상담소

풀이

def solution(start, end, price):
    items = [(e, s, p) for e, s, p in zip(end, start, price)]
    items.sort()

    dp = [0 for _ in range(max(end) + 1)]
    for e, s, p in items:
        for j in range(e, len(dp)):
            dp[j] = max(dp[s] + p, dp[j])
    
    return dp[-1]

Testcase

# 테스트 1
입력값 〉 [1, 5, 10, 6, 5], [5, 6, 12, 9, 12], [10, 40, 30, 20, 50]
기댓값 〉 100

# 테스트 2
입력값 〉 [1, 2, 5, 1, 4, 11], [10, 9, 6, 3, 9, 15], [50, 20, 50, 20, 80, 40]
기댓값 〉 140

2. 삽질의 대가

풀이

def solution(depth, n, blocks):
    width = len(blocks[0])

    dp = [[float('inf')] * width for _ in range(depth + 1)]

    for j in range(width):
        dp[0][j] = blocks[0][j]

    for d in range(1, depth + 1):  
        for j in range(width):  
            min_energy = dp[d-1][j]  
            if j > 0:
                min_energy = min(min_energy, dp[d-1][j-1])  
            if j < width - 1:
                min_energy = min(min_energy, dp[d-1][j+1])
            
            dp[d][j] = blocks[d][j] + min_energy

    return dp[depth][n]

Testcase

# 테스트 1
입력값 〉 3, 3, [[5, 6, 2, 6], [1, 6, 4, 9], [5, 6, 9, 4], [55, 14, 21, 14]]
기댓값 〉 24

3. 한 번의 거짓말

풀이

from heapq import heappop, heappush

def solution(N, friend, time):
    visited = [False for _ in range(N)]

    def dfs(node):
        if visited[node]:
            return
        
        visited[node] = True
    
        if all(visited):
            return
    
        for f in friend[node]:
            dfs(f)
    
    dfs(0)

    if not all(visited):
        return -1
    

    def dijkstra(node):
        heap = []
        distances = [float('inf') for _ in range(N)]
        
        heappush(heap, (0, node))
        distances[node] = 0
        
        while heap:
            d, i = heappop(heap)
            if distances[i] < d:
                continue
            for f, t in zip(friend[i], time[i]):
                new_dist = d + t
                if distances[f] > new_dist:
                    distances[f] = new_dist
                    heappush(heap, (new_dist, f))
        
        return distances
    
    dists = dijkstra(0)
    return max(dists)

Testcase

# 테스트 1
입력값 〉 5, [[1, 4], [2, 3], [4], [1], [0, 2]], [[5, 2], [6, 4], [9], [1], [2, 6]]
기댓값 〉 9

4. 제한된 비행편

풀이

from heapq import heappush, heappop

def solution(N, flight, a, b, k):
    adj_list = [[] for _ in range(N)]
    for src, dst, price in flight:
        adj_list[src].append((dst, price))

    best_cnt = [float('inf') for _ in range(N)]
    heap = [(0, 0, a)]

    while heap:
        price, count, node = heappop(heap)

        if best_cnt[node] < count:
            continue
        
        best_cnt[node] = count

        if count > k:
            continue

        if node == b:
            return price
        
        for adj_node, add_price in adj_list[node]:
            heappush(heap, (price + add_price, count + 1, adj_node))
    
    return -1

Testcase

# 테스트 1
입력값 〉 4, [[0, 2, 1], [1, 3, 20], [1, 0, 8], [2, 3, 1], [0, 3, 3]], 1, 3, 2
기댓값 〉 11

5. 전광판 컨트롤

풀이

LINES = []

LINES.append('##### --#-- #### #### #---# ##### ##### ##### ##### #####'.split(' '))
LINES.append('#---# --#-- ---# ---# #---# #---- #---- ----# #---# #---#'.split(' '))
LINES.append('#---# --#-- #### #### ##### ##### ##### ----# ##### #####'.split(' '))
LINES.append('#---# --#-- #--- ---# ----# ----# #---# ----# #---# ----#'.split(' '))
LINES.append('##### --#-- #### #### ----# ##### ##### ----# ##### ----#'.split(' '))

def solution(n):
    digits = list(map(int, list(str(n))))

    lines = [[] for _ in range(len(LINES))]
    for digit in digits:
        for i in range(len(lines)):
            lines[i].append(LINES[i][digit])
    
    for i in range(len(lines)):
        lines[i] = ' '.join(lines[i])
    
    return lines

Testcase

# 테스트 1
입력값 〉 132
기댓값 〉 ["--#-- #### ####", "--#-- ---# ---#", "--#-- #### ####", "--#-- ---# #---", "--#-- #### ####"]

# 테스트 2
입력값 〉 857
기댓값 〉
["##### ##### #####", "#---# #---- ----#", "##### ##### ----#", "#---# ----# ----#", "##### ##### ----#"]
실행 결과 〉
실행한 결괏값 []이 기댓값 ["##### ##### #####","#---# #---- ----#","##### ##### ----#","#---# ----# ----#","##### ##### ----#"]과 다릅니다.

출처

해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.

모든 자료는 저작권법에 의하여 보호받는 저작물로서 이에 대한 무단 복제 및 배포를 원칙적으로 금합니다.