https://www.acmicpc.net/problem/1516 접근 방법 전에 풀었던 문제와 비슷하다. 시간을 계속 누적하면서 더하면 된다. 이 때 시간의 최댓값이 나와줘야 하므로 밑의 코드처럼 체크를 해주었다. if(ans[nv] < build_time[nv] + ans[vertex]){ ans[nv] = build_time[nv] + ans[vertex]; } Need Know 위상 정렬 전체 코드 ( Java ) import java.io.*; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Main { static Buffere..

https://www.acmicpc.net/problem/14567 접근 방법 간단한 위상정렬 문제이다. Queue를 넣을 때 Level이라는 속성을 넣어주면 쉽게 풀 수 있다. Need Know 위상 정렬 전체 코드 ( Java ) import java.io.*; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedW..

https://www.acmicpc.net/problem/2056 접근 방법 문제에서 작업을 하는데에 있어서 순서가 있다고 하였다. 작업을 하기 전에 끝내야 할 것이 있으므로 위상 정렬을 사용하기로 했다. degree 가 0 ( 선행 조건을 다 수행을 하였다 ) 이 된 값 들을 queue에 넣어주는 방법. 그리고 tmp 배열을 사용한 이유는 각 작업을 끝내기 위해 필요한 누적 소요 시간을 저장을 따로 해줘야 되기 때문이다. Need Know 위상 정렬 전체 코드 ( Java ) import java.io.*; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokeni..

https://www.acmicpc.net/problem/17070 접근 방법 간단하다. 그냥 재귀 함수를 통해서 현재 상태값과 현재의 위치에서 갈 수 있는 모든 것들을 넣어주 면 된다. 물론 나의 코드는 dp를 사용해서 반복되는 구간을 처리하고 있지 않지만 시간 초과가 일어난다면 DP 를 사용해야 할 것이다. ( 제 친구가 pypy를 쓰는데 시간초과가 났다고 함... ) Need Know 재귀함수 필요에 의하면 동적프로그래밍 (DP) 전체 코드 ( Java ) import java.io.*; import java.util.StringTokenizer; class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(Syst..

https://www.acmicpc.net/problem/2437 접근 방법 아이디어만 있다면 풀 수 있는 문제이다. 물론... 그 기발한 아이디어가 없어서 질문 검색을 통해 그 아이디어를 얻게 되었다. 아이디어는 이러하다. 먼저 n번째 까지의 누적값을 Sn 이라 해보자. 그리고 배열에서 n번째 값을 An 이라 하자. 그리고 S(n-1) 보다 만약 (An)-1값이 크면 S(n-1) ~ A(n-1) 의 값은 만들지 못한다. 따라서 만들 수 없는 최솟값은 S(n-1) 이 된다. 내가 생각하는 증명은 이러하다. Sn은 1부터 시작할 것이다. 왜냐하면 첫번째 원소가 2라면 제일 최솟값인 1을 만들지 못하기 때문이다. 그럼 이제 차근차근 값들이 더 해가지면서 만들 수 있는 조합들이 무수하게 많아질 것이다. 하지만..

https://www.acmicpc.net/problem/3671 접근 방법 먼저 문제를 보았을 때 배열에 대한 순열이 필요하다는 것을 알았다. 하지만 여기서 평범하게 순열을 쓰면 { 1, 1, 1 } 에서 1번째 1 + 2번째 1 → 11 / 2번째 1 + 3번째 1 → 11 두 개의 값은 다르다고 인식을 할 것이다. 그렇기 위해 나는 어떠한 장치를 걸기로 하였다. 맨 처음에는 단순히 Visit을 배열로 생성하고 boolean타입으로 한 번 들렸다면 true값을 반환하게 만들었었다. 하지만 문제의 메모리 제한은 128 MB 이다. 그래서 메모리 초과가 발생하게 된다. ( 10000000 boolean타입이 두개 이기 때문에 ) 해결방법은 3번, 4번 을 읽기를 바란다. Decimal_arr (에라토스테..