240402 - 감시, 트리의 지름, 자두나무

[robert-min]

문제

1. boj15683 - 감시 링크
2. boj1967 - 트리의 지름 링크
3. boj2240 - 자두나 링크

[robert-min]

boj15683 - 감시

• 정답 풀이 링크

• 내 풀이(오답)

  
  """
  Return : 사각 지대의 최소 크기

• CCTV가 최대한 넓은 범위를

• CCTV가 회전 함에 따라 확인하는 범위가 달라짐

  • 회전 했을 때, 경우의 수 확인

• CCTV가 배치되었을 때, 사각 지대 확인

• area = [[]]

• 모든 CCTV 확인 dfs

  • num == len(cctv) -> max_area 계산

• CCTV 번호에 따라 감시되는 영역 확인 check

  • dfs """ import sys input = sys.stdin.readline N, M = map(int, input().split()) matrix = [] cctv = [] for i in range(N): row = list(map(int, input().split())) for j, val in enumerate(row): if 0 < val < 6: cctv.append((i, j)) matrix.append(row)

def find_blank(area): cnt = 0 for i in range(N): for j in range(M): if area[i][j] == 0: cnt += 1 return cnt

print(find_blank(matrix))

def find_cctv(area, x, y, dir): temp = [a[:] for a in area] for d in dir: nx, ny = x + dx[d], y + dy[d] while 0 <= nx < N and 0 <= ny < M and matrix[nx][ny] == 0: temp[nx][ny] = 1 nx += dx[d] ny += dy[d] return temp

남, 동, 북, 서

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

direction = { 1: [[0], [1], [2], [3]], # 1번cctv 방향:0, 1, 2, 3, --> 4가지 2: [[0, 2], [1, 3]], # 2번cctv 방향:(0, 2), (1, 3) --> 2가지 3: [[0, 1], [1, 2], [2, 3], [3, 0]], # 3번cctv 방향:(0, 1), (1, 2), (2, 3), (3, 0) --> 4가지 4: [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]], # 4번cctv 방향... 4가지 5: [[0, 1, 2, 3]] # 5번cctv 방향... 1가지 }

min_area = N * M def dfs(idx, area): global min_area if idx == len(cctv): blank_area = find_blank(area) min_area = min(min_area, blank_area) else: x, y = cctv[idx] flag = matrix[x][y] for dir in direction[flag]: temp = find_cctv(area, x, y, dir) dfs(idx + 1, temp)

area = [m[:] for m in matrix] dfs(0, area) print(min_area)

[robert-min]

boj1967 - 트리의 지름

"""
Return : 트리의 가장 먼 노드 사이의 거리 출력
- 지름은 특정 노드에서 다른 노드까지의 거리를 의미

[[(자식노드, 거리), (자식노드), 거리], ...]

- 루트노드에서 가장 거리가 먼 노드를 찾음
- 해당 노드에서 가장 거리가 먼 노드를 찾을 때 그 거리가 가장 긴 지름
"""
import sys
input = sys.stdin.readline

N = int(input())
trees = [[] for _ in range(N+1)]

for _ in range(N-1):
    u, v, dist = map(int, input().split())
    trees[u].append((v, dist))
    trees[v].append((u, dist))
# print(trees)

# 시작 정점에서 임의의 정점까지 가장 먼 정점
visited = [-1] * (N+1)
def dfs(start, dist):
    for nx, nx_dist in trees[start]:
        if visited[nx] == -1:
            visited[nx] = dist + nx_dist
            dfs(nx, dist + nx_dist)

visited[1] = 0
dfs(1, 0)
# print(visited)

# 가장 먼 노드를 시작 지점으로 가장 긴 거리 찾음
last_node = visited.index(max(visited))
visited = [-1] * (N+1)
visited[last_node] = 0

dfs(last_node, 0)
print(max(visited))

[robert-min]

boj2240 - 자두나무

import sys

# 자두가 떨어지는 시간 T와 이동할 수 있는 횟수 W
t, w = map(int, sys.stdin.readline().rstrip().split(" "))

# 자두가 떨어지는 나무의 번호 저장
arr = [0]
for _ in range(t):
    arr.append(int(sys.stdin.readline()))

# 2차원 DP 테이블 초기화
dp = [[0] * (w+1) for _ in range(t+1)]

for i in range(t+1):

    # 1번 나무에서 한 번도 움직이지 않는 경우

    # 1번 나무에서 자두가 떨어진다면
    if (arr[i] == 1):
        dp[i][0] = dp[i-1][0] + 1

    # 2번 나무에서 자두가 떨어진다면
    else:
        dp[i][0] = dp[i-1][0]

    # 1번 이상 움직이는 경우에 대해 탐색
    for j in range(1, w+1):

        # i초에 2번 나무에서 자두가 떨어지고, 현재 2번 나무에 위치해있다면
        if (arr[i] == 2 and j % 2 == 1):
            # 이전 위치로부터 움직여서 받아 먹을 것인지, 현재 위치에서 받아 먹을 것인지를 비교
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + 1

        # i초에 1번 나무에서 자두가 떨어지고, 현재 1번 나무에 위치해있다면
        elif (arr[i] == 1 and j % 2 == 0):
            # 이전 위치로부터 움직여서 받아 먹을 것인지, 현재 위치에서 받아 먹을 것인지를 비교
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + 1

        # i초에 자두가 떨어지는 나무와 현재 나무의 위치가 다르다면
        else:
            # 움직여서 못 먹는 경우와 움직이지 않아서 못 먹는 경우를 비교
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])

# DP 테이블의 마지막 행의 최댓값을 출력
print(dp)
print(max(dp[t]))