김머성 블로그

[BAE/<JOON> 문제풀이] 13325. 이진 트리

https://www.acmicpc.net/problem/13325 13325번: 이진 트리 입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가 www.acmicpc.net 핵심 :: 루트 정점에 근접한 정점에 비용을 추가 할 수록 전체 추가 비용이 줄어든다. ( 그 정점 아래의 모든 리프 노드에 비용이 추가되므로 ) 간선에 비용을 늘릴수밖에 없으므로 가장 먼 리프 노드를 찾고 그 거리를 기준으로 다른 경로에 비용을 추가하면 된다. 풀이 :: DP[x] = x 정점 아래 리프 노드 중 가장 먼 리프 노드까지의 거리 현재 간선에 필요한 값 = p 1번 정점부터 아..

[BAE/<JOON> 문제풀이] 15681. 트리와 쿼리

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 핵심:: 문제 힌트 풀이:: DP[정점 번호] = 자식 정점 개수 트리를 구성하고 탑다운 방식으로 정점 갯수를 센다. 사실 DP 배열에 저장할 필요도 없는게, 트리 구조라서 각 정점은 한번씩만 방문되기 때문에 메모이제이션 할 필요도 없다. 근데 왜 동적계획법 태그가 붙었는지 잘 모르겠다. 의견:: 기본문제 코드:: 더보기 #includ..

[BAE/<JOON> 문제풀이] 10217. KCM Travel

https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 핵심:: DP 메모이제이션 풀이:: 문제 보자마자 제한 시간 10초길래 흠칫했다. 제한된 비용(간선 비용)으로 목적지에 도착하는 최소 거리(시간)를 구하는 문제다. DP[현재 도시][사용한 비용] = 최소 시간 최소힙을 사용해 다익스트라를 구현하고 cost 배열에 출발지부터 현재 도착지까지 올 때 사용할 수 있는 가장 적은 비용을 저장한다. 이 때, 다양한 비..

[BAE/<JOON> 문제풀이] 2637. 장난감 조립

https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 핵심:: DP문제이긴 하지만 점화식 보다는 메모이제이션으로 중복 탐색 제거가 포인트 풀이:: DP[대상부품번호][필요부품번호] = 필요한 개수 우선 기본 부품은 진입 간선 수를 보고 미리 파악해둔다. 이 후, 탑-다운 방식으로 완제품에 필요한 부품에서 기본 부품으로 내려가며 필요한 부품 수를 파악한다. 단, 아래로 내려가면 중복 계산이 발생 할 수 있으므로 DP 배열에 ..

[BAE/<JOON> 문제풀이] 13141. Ignition

https://www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 핵심:: 간선 별로 다 태우는 시간을 구하는 공식을 생각해보면 된다. 풀이:: 플로이드 알고리즘으로 모든 정점에 불이 도착하는 가장 빠른 시간을 n3 시간에 구할 수 있다. 간선의 양 끝 정점에 불이 도착하는 가장 빠른 시간을 a, b라고 하고 간선의 길이를 e라고 하면 간선이 다 타는 시간은 (e - abs(a - b) / 2) + max..

[BAE/<JOON> 문제풀이] 1006. 습격자 초라기

https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 드디어,, 이 문제를 풀었다,, PS 공부 처음 시작해서 문제 순서대로 풀 때 딱 이 문제에서 막혔었는데 푸는 날이 오고야 말았다. 핵심:: 환형 DP -> 이 유형을 가리키는 정확한 용어가 있는지는 모르겠다. 배열의 앞뒤를 붙이고 푸는 문제 유형이 있는 것 같다. 이 문제를 풀기 전에 프로그래머스에 있는 도둑 문제를 풀어보면 도움이 된다. 풀이:: 지..