코딩테스트 대비 백준 문제 뽀개기 : 최근 빈출 유형
1. ACM Craft
https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
- 문제: 건물을 빨리 지을 수록 이기는 게임이다. 건물을 짓기위한 순서가 정해져 있으며 각 건물을 짓는데 필요한 시간이 다르다고 할 때 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성하라
- 해결방안: 위상정렬 + DP
# 위상정렬: visited, 단방향 그래프(graph), 진입차수리스트(indegree), 큐(deque)가 필요하다!!1
# 하지만 이번 위상정렬에선 visited쓰지 말고 dp배열에 최댓값들을 저장해야 한다. .! (최소값을 구해야 하므로 각 시점마다의 최솟값을 갱신해야 한다.)
- 주의 사항:
#노드나 그래프 번호가 있는 문제는 0~N말고 0~N+1까지 정의하자!!
# 문제에선 최소시간이지만 값은 "최댓값을 구해야 한다!!1" dp[i]가 해당 건물까지 걸리는 시간이므로 직전에 짓는 건물들이 무조건 끝나야 한다!

#위상정렬: visited, 단방향 그래프, 진입차수리스트, 큐가 필요하다!!1
#노드나 그래프 번호가 있는 문제는 0~N말고 0~N+1까지 정의하자!!
# 이번 위상정렬에선 "visited쓰지 말고 dp배열에 최댓값들을 저장해야 한다. .! why
from sys import stdin
from collections import deque,defaultdict
input = stdin.readline
if __name__ == "__main__":
T = int(input())
for _ in range(T):
N, K = map(int,input().split())
answer = 0
building = [0]
building.extend( list(map(int,input().split())))#건물의 건설시간
indegree = [0] * (N+1)
visited = [False] * (N+1)
dp = [ -1 for _ in range(N+1)] #해당 건물까지 걸리는 시간
order = defaultdict(list)
#건물 별 인접관계 정보 저장
for _ in range(K):
a,b = map(int,input().split())
order[a].append(b)
indegree[b] += 1
#마지막 건물 번호 저장
W = int(input())
#진입 차수가 0인 빌딩 삽입
q = deque()
for i in range(1,N+1):
if indegree[i] == 0:
q.append(i)
dp[i] = building[i]
while q:
cur = q.popleft()
for x in order[cur]:
indegree[x] -= 1 #진입차수 줄이고 비용 갱신
dp[x] = max( dp[x], dp[cur] + building[x] ) # 기존의 최댓값과 이번에 지을 건물의 비용 중 큰 값 선택
if indegree[x] == 0:
q.append(x)
print(dp[W])
2. 사회망 서비스(SNS)
- https://www.acmicpc.net/problem/2533
2533번: 사회망 서비스(SNS)
페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망
www.acmicpc.net
- 문제: 회망 서비스에 속한 사람들은 얼리 아답터이거나 얼리 아답터가 아니다. 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 친구 관계 트리가 주어졌을 때, 모든 개인이 새로운 아이디어를 수용하기 위하여 필요한 최소 얼리 어답터의 수를 구하는 프로그램을 작성하시오.
- 해결방안 : DP
# 특정 노드는 얼리 어답터이거나, 그냥 일반인인데, 두 state는 완전히 독립적이므로, 다이나믹 프로그래밍의 적용이 가능하다.
dp[node][0] : 해당 노드가 얼리 어답터일 경우, 본인 노드 + 해당 노드의 모든 자식노드 중 문제 조건을 만족하는 최소얼리어답터 수
dp[node][1] : 해당 노드가 일반인일 경우 자식 노드가 얼리어답터일 대 만족하는 최소 값
- 주의 사항
# 트리로 주어진다 해도, (a,b)의 입력값이 항상 a가 부모란 전제가 없을 경우, 그래프는 "양방향"으로 그리자! 그리고 대신 해당 노드를 방문했는지 판단하는 visited를 꼭꼭 처리하자!!!!
# dp 구하는 함수를 첨 시작할 때 매개변수로!!! 리턴하기!!! ex) solution(1)했으면 정답도 dp[1]에 있는거임
# solution함수의 매개변수에 따라 dp리턴값이 다른 경우(예를들어, solution(1,0), solution(1,1)둘다 해야하는 경우) 리턴값은 min (solution(1,0),solution(1,1))과 같은 형식으로 반환하는게 좋다

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
INF = sys.maxsize
N = int(input())
graph = [ [] for _ in range(N+1)] #양방향 그래프
dp = [ [INF,INF] for _ in range(N+1) ] #[정점번호][얼리어답터 체크]
visited = [False] * (N+1)
#그래프 입력
for _ in range(N-1):
u, v = map(int,input().split())
graph[u].append(v)
graph[v].append(u)
def solution(num,idx):
if dp[num][idx] != INF:
return dp[num][idx]
else:
dp[num][0] = 1 #내가 얼리어답터일때
dp[num][1] = 0 #내가 일반인일때
for i in graph[num]:
if visited[i] == True:
continue
visited[i] = True
cmp1 = solution(i,0)
cmp2 = solution(i,1)
dp[num][0] += min(cmp1,cmp2) #내가 얼리어답터면 친구가 얼리어답터일경우,아닐경우 둘 중 작은값을 더함 (어차피 내가 얼리어답터이므로 상관없음)
dp[num][1] += cmp1 #내가 일반인이면 친구가 얼리어답터야 함
return dp[num][idx]
visited[1] = True
print( min(solution(1,0),solution(1,1)) )