Java/Algorithms

문제 접근 방식 주어진 수열에서 순서 상관 없이 수들을 더하거나 둘을 묶어서 곱하여 가장 큰 값을 얻기 위해서는 빼야 할 때는 가능한 가장 작은 수를 더해줄 때는 가장 큰 수를 더해줘야 한다. 두 수를 곱하는 경우를 생각해보면 음수 * 음수 = 양수 음수 * 0 = 0 양수 * 양수 = 양수 위와 같이 세 가지 경우가 있고 두 수를 더하는 경우를 생각해보면 양수 * 1 < 양수 + 1 양수 * 0 < 양수 + 0 위와 같은 경우가 있다. 좀 더 간단하게 정리해보면 아래와 같다. // 음수로 만들 수 있는 최적의 해 음수 * 0이하의 수 // 양수로 만들 수 있는 최적의 해 양수 * 양수 양수 + 1 양수는 0과 곱하거나 더하는 경우에는 어떤 이득도 볼 수 없기 때문에 0은 위와 같이 음수와 처리해주는 것..

문제 접근 방식 1 3 2 5 3 5 6 7 위와 같이 일직선 상의 선분의 시작점과 끝점이 주어졌을 때 시작점이 가장 작은 순으로 정렬하고 각 선분을 그어보면 세 가지 경우로 선분을 그을 수 있는데 1 2 3 4 5 6 7 1 3 2 5 3 5 6 7 위와 같이 처음 1-3 선분이 있을 때 다음에 오는 2-5 선분은 이전 1-3선분에 겹치면서 길이가 조금 더 긴 경우 3-5 선분은 이전 선분 자체에 모두 겹치는 경우 6-7 선분은 겹치지 않는 새로운 선분인 경우다. 완전히 새로운 경우에는 끝점 - 시작점으로 선분의 길이를 구할 수 있고 겹치는 경우에는 겹치지 않는 경우만 계산하면 되기 때문에 현재 선분의 끝점에서 이전 선분의 끝점을 빼주면 되고 완전히 겹치는 경우에는 계산할 필요가 없다. 풀이 publi..

문제 접근 방식 우선 문제를 정리해 보면 꽃이 피는 날과 지는 날이 주어졌을 때 피는 날을 포함한 날부터 꽃이 피기 시작하고 지는 날을 포함하지 않은 날까지 꽃이 피어있는다. 정원에 꽃이 하나라도 피어 있는 상태를 유지하기 위해선 이전에 핀 꽃이 지기 전이나 지자 마자 바로 다음 꽃이 피어 있어야 하기 때문에 이전에 심은 꽃들 중 가장 늦게 지는 날보다 전이거나 지는 당일에 꽃이 피는 경우에만 심을 수 있다. 10 2 15 3 23 4 12 6 5 5 2 5 31 9 14 12 24 6 15 9 3 6 3 6 15 2 28 4 25 6 15 9 27 10 5 12 31 7 14 9 1 위와 같은 입력이 주어졌을 때 꽃이 빨리 피는 순서대로, 같은 경우에는 빨리 지는 순서대로 먼저 정렬을 해준다. 2, 1..

문제 접근 방식 주어진 식에 적절히 괄호를 추가해 가장 작은 결과를 얻어야 하는데 간단하게 생각해 보면 - 부호가 등장한 이후에 나오는 모든 숫자들을 - 부호가 재등장하기 전까지 빼주면 된다. 55-50+40-50+40+30-50 예를 들어 위와 같은 식이 주어졌다면 55-(50+40)-(50+40+30)-(50) 이렇게 괄호를 추가해 계산하는 것이 가장 작은 결과를 얻는다. 55-((50+40)-(50+40+30)-(50)) 조금만 더 생각해 보면 첫 - 부호 등장 이후에 오는 모든 수들은 복잡하게 생각할 필요 없이 빼도 상관이 없다는 것을 알 수 있다. 그래서 처음으로 -부호가 등장하기 전까지만 값을 더해주고 이후에 오는 모든 수들은 빼주면 된다. 풀이 public class Main { public..

문제 접근 방식 싼 값에 주식을 사고 비싼 값에 팔면 가장 이득을 볼 수 있다는 당연한 사실을 통해 주어진 주가를 역으로 탐색해 현재 가장 큰 값보다 비싼 값을 만날 때까지 이전의 모든 주식을 산 후에 팔아주면 된다. 3 2 4 5 7 8 6 9 8 4 5 예를 들어 위와 같이 주가 목록이 주어졌을 때 역으로 탐색하면 5를 기준으로 더 큰 값인 8을 만나기 전까지 주식을 사면 4원에 주식을 산 후에 5원에 팔아서 1원 이득을 볼 수 있고 다시 8을 기준으로 더 큰 값이 9를 만나기 전까지는 어떠한 주식도 살 수 없기 때문에 8을 그대로 팔아 0원 이득을 볼 수 있으며 다시 9를 기준으로 더 큰 값이 없으므로 남은 모든 주식을 사면 (9원 * 7일) - (3 + 2 + 4 + 5 + 7 + 8 + 6) =..

문제 접근 방식 10, 30, 20, 50, 40, 80, 70, 60 만약 위와 같은 로프들이 주어졌을 때를 생각해보면 8개의 로프를 모두 사용한 경우에는 가장 낮은 무게를 들 수 있는 10kg짜리 로프에 맞춰야하기 때문에 80kg를 들 수 있지만 7개를 사용하는 경우에는 20kg에 맞춰서 140kg을 들 수 있다. 10, 20, 30, 40, 50, 60, 70, 80 80, 140, 180, 200, 200, 180, 140, 80 정렬을 해서 n개의 추를 사용하는 경우를 모두 계산해보면 위와 같다. 결국 정렬을 한 후에 n개를 골랐을 때마다 가능한 무게를 계산하고 그 중에서 가장 큰 값이 정답이 된다. 풀이 public class Main { public static void main(String..

문제 접근 방식 DP를 이용해서 O(N^2) 풀이를 생각할 수도 있지만 주어진 입력과 제한 시간으로는 해당 시간 복잡도로는 풀 수 없는 문제다. 간단하게 생각해 보면 가장 많은 회의를 배정하기 위해서는 가장 빨리 끝나는 회의들만 골라주면 된다. 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 위의 경우를 예로 들면 첫 번째 회의가 가장 빠른 4시에 끝나니 이 회의를 고른 후에 다음으로 4시 이후에 시작하는 다른 회의를 골라야 가장 효율적으로 회의를 배정할 수 있는 것을 알 수 있다. 1, 4 3, 5 0, 6 5, 7 3, 8 5, 9 6, 10 8, 11 8, 12 2, 13 12, 14 위는 주어진 회의 시간들을 끝나는 시간이 가장 빠른 순으로 정렬하고 끝나는..

문제 접근 방식 문제 자체는 간단한데 어떻게 풀어야 할지 어려웠던 문제였지만 일단 규칙을 찾아야 할 거 같아서 수들을 적다 보니 특징을 발견해서 풀 수 있었다. 110101 212121 123 321210 212 423232 234 532 634 743 845 954(생략) 56 65 67 76 78787 789 87876 878 89898 98987 989 각각 한 자리부터 세 자리까지의 쉬운 계단 수를 나열한 목록인데 0과 9로 끝나는 부분만 제외한 모든 수들이 2배씩 늘어나고 0과 9로 끝나는 경우만 그대로 하나인 것을 알 수 있다. 0으로 끝나는 경우에는 09가 될 수 없으니 01만 올 수 있고 9로 끝나는 경우도 마찬가지로 90이 될 수 없으니 98만 올 수 있다. 0과 9를 제외한 1~8로 끝..