문제 백준 11399 N(1…1000)명의 사람이 돈을 인출하는데 걸리는 시간 Pi(1…1000) 이 각각 주어진다고 할 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최소값을 구하시오. 주의 : i번째 사람이 돈을 인출하는데 필요한 시간은 1...i-1번째 사람을 기다리는 대기 시간도 포함한다. 예시 : P1 = 3, P2 = 1, P3 = 4일 때, [1, 2, 3]순서로 돈을 뽑을 때는 3 + (3 + 1) + (3 + 1 + 4) = 15의 시간이 걸린다. [2, 1, 3]순서로 돈을 뽑아야 1 + (1 + 3) + (1 + 3 + 4) = 13인 최소값이 나온다. 해결 아주 쉬운 문제이다. 대기시간을 줄이는게 관건이다. 즉, 시간을 오름차순으로 정렬하여 앞에서 부터 사용 시간 = 이전 값(..

[백준(baekjoon) 11047] 동전 0 문제 백준 11047 N개의 종류의 동전의 가치 Ai가 주어질 때 (각 종류의 동전은 무한히 많다.) 동전 들을 사용해 K원을 만들려고 한다. 이때, 필요한 동전 종류 개수의 최소 값은? 주의 : A1 = 1은 Default이며, i > 1을 만족하는 Ai = Ai-1의 배수이다. 해결 처음에는 DP를 사용해야 하나 했다. N = 3, K = 2000, A1 = 100, A2 = 500, A3 = 800의 경우 정답은 A2 * 4 = 2000이 되기 때문에. 하지만, 역시 문제는 자세히 읽어야 한다…! i > 1을 만족하는 Ai = Ai-1의 배수이다. 이 부분에 의해서 그리디 알고리즘으로 문제를 해결할 수 있다. 가장 큰 동전 종류부터 확인, 차액을 구하여..

문제 백준 1912 n(1…100,000)과 n의 크기를 가진 수열이 주어질 때, 연속된 숫자들의 합 중 최대 값을 출력하라. 예시 : {10, -4, 3, 1, 5, 6, -35, 12, 21, -1}일 때, 12+21인 33이 정답이 된다. 해결 간단하게 앞에서 부터 시작해서 각 값으로 끝나는 연속된 수열의 최대 합을 구하면 된다. 자신으로 시작하는 경우 이전 연속 수열에 자신을 포함하는 경우 이렇게 두 가지의 경우로 나눌 수 있으므로, 두 값을 비교해서 큰 값을 저장하면 된다. 시간복잡도는 O(N)이다. 알고리즘 DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 구현 java Top-down 방식 1.imp..

[백준(baekjoon) 11054] 가장 긴 바이토닉 부분 수열 문제 백준 11054 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 바이토닉 부분 수열 중 가장 긴 길이를 출력. 바이토닉 수열 : S1 Sk+1 > … SN-1 > SN을 만족하는 수열 예시 : {10, 20, 30, 25, 20}, {10, 20, 30, 40}, {50, 40, 25, 10} 주의 : 증가, 감소 수열도 바이토닉 수열에 속한다. 해결 가장 긴 증가하는 부분과 매우 유사한 문제이다. 2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다. 최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다. 여기서 다른 점은, 증가하는 부분과 감소하는 ..

[백준(baekjoon) 11722] 가장 긴 감소하는 부분 수열 문제 백준 11722 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 수열에서 감소하는 부분 수열 중 가장 긴 길이를 출력. 예시 : A = {10, 30, 10, 20, 20, 10} 인 경우, A = {30, 20, 10} 이고 길이는 3이다. 해결 가장 긴 증가하는 부분과 매우 유사한 문제이다. 2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다. 최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다. 알고리즘 DP로 풀었고, bottom-up 방식으로만 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 구현 java Bottom-Up 방식 1.import java.u..

문제 백준 11055 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 수열에서 증가하는 부분 수열 중 가장 큰 합을 출력. 예시 : A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우, A = {1, 2, 50, 60} 이고 합은 113이다. 해결 가장 긴 증가하는 부분과 매우 유사한 문제이다. 이것도 마찬가지로! 2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다. 최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다. 그러므로 일일이 구한 후 MAX 값을 찾아내면 끝! 알고리즘 DP로 풀었고, bottom-up 방식으로만 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 구현 java Bottom-Up 방식 ..