[백준] 2805, 1987

나무 자르기 (2805번)

• 사이트/난이도: 백준/실버2
• 코드

# 실버2 나무 자르기
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
heights = list(map(int, input().split()))

def get_height(h):
    result = 0
    for height in heights:
        if height > h:
            result += height - h
    return result

def binary_search(start, end):
    answer = 0
    while start <= end:
        mid = (start + end) // 2
        h = get_height(mid)
        if h == m:
            answer = mid
            break
        elif h > m:
            start = mid + 1
            answer = mid
        elif h < m:
            end = mid - 1
    return answer

print(binary_search(0, max(heights)))

• 느낀점
  • 기본적인 이진탐색 문제
  • 여기서 한번 더 생각해야 되는 부분은 자르려는 나무의 최대 높이를 구해야 하므로 answer 변수를 따로 두어서 h 가 m 이상아면 계속 answer에 mid를 바꿔주면서 최대 높이를 구하면 된다.
  • 살짝 헤멘게 binary_search 에 start변수를 넣을때 0 을 넣어야 되는데 아무 생각없이 min(heights) 를 넣었다가 몇번 실패했다.

알파벳 (1987번)

• 사이트/난이도: 백준/골드4
• 코드

# 골드4 알파벳
r, c = map(int, input().split())
graph = [list(input()) for _ in range(r)]
history = set()

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

answer = 0

def dfs(x, y):
    global answer
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c:
            if graph[nx][ny] not in history:
                history.add(graph[nx][ny])
                dfs(nx, ny)
                history.discard(graph[nx][ny])
    answer = max(answer, len(history))

history.add(graph[0][0])
dfs(0,0)
print(answer)

• 느낀점
  • dfs + 백트랙킹 문제
  • 처음에 history를 list로 만들었더니 in 연산과 remove 연산이 O(n) 만큼 걸려서 계속 시간 초과가 났다.
  • set으로 하면 두 연산이 모두 O(1) 로 되기 떄문에 이를 통해 해결했다.