전체 글

문제 링크 : https://www.acmicpc.net/problem/1744 위의 문제는 주어진 수열에서 수끼리 묶거나(곱하거나) 또는 그냥 더해서 최대합을 구하는 문제입니다.최댓값을 구하기 위해서는 양수에서는 가장 큰 값과 그다음으로 큰 값을 곱해서 더하는 게 좋지만 만약 해당 양수가 1일 경우에는곱하지 않고 그냥 더하는 게 더 큰 값이 됩니다. 음수에서는 내림차순으로 정렬하여 가장 작은 값과 그다음 작은 값을 곱해 더해줘야 합니다.양수와는 다르게 음수에서는 -1이라고 하더라도 무조건 음수와 곱해준 뒤 더해주는 게 더 큰 값을 더할 수 있습니다.이때 만약 같은 음수에서 짝지을 수가 없을 경우 0이 있다면 0과 곱해주는 것이 더 큰 값을 더할 수 있게 됩니다. 따라서 0보다 큰 양의 정수를 모은 pl..

문제 링크 : https://www.acmicpc.net/problem/1715 문제를 처음 접하고 예제 입력만을 가지고 단순히 생각해 보면 숫자 카드 묶음을 1차원 배열로 만들고 이를 오름차순 정렬해서 앞에서부터 더해 나가면 되지 않을까 생각할 수 있지만그건 오름차순으로 정렬하고 가장 작은 값들 2개를 골라 더한뒤 그다음 작은 값이 배열의 다음 값인 경우에만 가능하다예를 들어 문제의 예제처럼 10, 20, 40 일 경우에는(10 + 20) = 30 이고 해당 값 다음으로 큰 값이 40이기 때문에 단순 1차원 배열에서 오름차순 정렬로 풀 수 있다. 하지만 만약 주어진 카드 묶음이 10, 10, 10, 10, 10이라고 하면오름 차순 정렬 후 가장 작은 2개의 값은 10, 10 이기때문에 둘을 합치면 20..

문제 링크 : https://www.acmicpc.net/problem/1300 문제를 풀어서 보면 단순히 2차원 배열의 값들을 1차원 배열로 옮겨서 오름차순으로 정렬한 뒤K번째 인덱스(1부터 시작)의 값을 출력하면 되는 문제다. 하지만 N의 값이 최대 10^5 이기 때문에 이를 2차원 배열 N*N으로 만든다면 최대 10^10 개의 값들이 생성된다.따라서 단순히 2차원 배열의 값을 1차원 배열로 옮겨서 해결할 수는 없다. 따라서 다른 풀이를 생각해야 한다.먼저 문제 조건에 따라 3 * 3 배열을 1차원 배열로 전환하고 오름차순 정렬하면1 2 2 3 3 4 6 6 9가 되는 것을 알 수 있다.이때 K번째 인덱스의 값은 절대 K값 이상이 될 수 없다는 것을 알 수 있다. 따라서 K번째 인덱스의 최댓값은 K,..

문제 링크 : https://www.acmicpc.net/problem/2343 연속된 배열에서 M개의 블루레이에 모든 기타 강의 동영상을 녹화할 때 블루레이의 최소 크기를 구하는 문제다.N이 100,000 이기 때문에 완탐은 불가능하고강의의 순서는 변경되지 않는다는것에서 이진탐색을 사용하면 풀 수 있다는 힌트를 얻어야 한다. 이진탐색의 시작과 끝 인덱스를 찾아야 하는데여기서 시작인덱스는 주어진 강의중 가장 시간이 긴 강의의 시간(만약 블루레이의 개수 M 이 N이라고 한다면 블루레이 하나당 최소한의 크기는 N개의 강의중 가장 시간이 긴 강의가 되기 때문) 끝 인덱스는 만약 M이 1이라고 한다면 모든 강의를 전부 포함해야 하기 때문에 모든 강의시간들의 합이 끝 인덱스가 된다. 따라서 시작 인덱스(가장 시간..