BOJ 4792 - 레드 블루 스패닝 트리 문제 링크(Link)https://www.acmicpc.net/problem/4792 문제 해결(Solution) MST를 두 번 생성해서 문제를 해결할 수 있다. 1. min_blue : R 간선을 우선으로해서 MST를 만들었을 때, 포함되는 B 간선의 개수 2. max_blue : B 간선을 우선으로해서 MST를 만들었을 때, 포함되는 B 간선의 개수 3. Answer : min_blue 더보기 BOJ 9084 - 동전 문제 링크(Link)https://www.acmicpc.net/problem/9084 문제 해결(Solution) DP로 문제를 해결한다 1. DP[n][m] : n번 째로 입력받은 동전에서 금액이 m일 때의 방법의 수 (TOP-DOWN) 2. DP[m] : 금액이 m일 때의 방법의 수 (BOTTOM-UP) 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 왜 TOP-DOWN 방식과 BOTTOM-UP 방식일 때의 DP table의 차원 수가 다를까? : BOTTOM-UP 방식일 때는 이중 for loop을 사용해서 동전 조합의 중복을 막을 수 있지만, TOP-DOWN 방식은 동전 조합의 중복을 막기 위해선 입력받은 동전의 순서를 저장해야한다. 그러므로 TOP-DOWN의 DP.. 더보기 BOJ 14863 - 서울에서 경산까지 문제 링크(Link)https://www.acmicpc.net/problem/14863 문제 해결(Solution) DP로 문제를 해결한다(DP table에 따라서 달라지는 수행 시간 비교). 1. DP[n][flag][limit] : n번 째 지점 n+1번 째 지점으로 이동 중 flag(0 : 도보 이용 , 1 : 자전거 이용)면서 소요 시간은 limit일 때의 최대 모금액. 2. DP[limit] : 소요 시간이 limit일 때의 최대 모금액. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 어떻게 3차원 DP table을 1차원으로 줄일 수 있을까? : 항상 최종 목적지에 도착할 수 있는 조건과 1번 지점부터 N번 지점까지 차례로 이동한다는 점과 어느 교통 수단을 이.. 더보기 이전 1 2 3 4 5 6 7 ··· 32 다음