김머성 블로그

[BAE/<JOON> 문제풀이] 1028. 다이아몬드 광산

https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 서론:: 이게 왜 DP 일까 ? 설마 부분합 구하는 그 부분 때문에 DP라고 하는건 아니겠지 ? 아니면 DP를 이용하는 풀이가 따로 있는 걸지도 모르겠다. 아이디어:: 문제를 보자마자 떠오르는 아이디어는 비숍 문제에서 봤던 대각선을 수직선으로 치환하는 방법이었다. ( 짝수 행렬과 홀수 행렬은 서로에게 영향을 미치지 않으므로 시작부터 이 둘을 구분한 2개의 배열을 만들고 풀이를 진행한다. ) 두 행렬을 만들고 거기에 어떤 DP 알고리즘을 적용하면..

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

https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 www.acmicpc.net 재채점 터져서 다시 푸는데 너무 힘들었다. 핵심:: 최적값이 아니어도 탐색 줄기를 유지해야하는 문제이다. 모든 최적값이 아닌 값들을 통과시키는 경우 TLE를 피할 수 없으므로, 최적값이 아닌 탐색들 중 유지시킬 줄기를 선택하는 기준을 정하는게 메인 아이디어인 문제이다. ( Simulate Anealing ? ) 이 풀이에서는 [사용한 비용과 경과된 시간] 이..

[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 배열에 ..