Java

문제 접근 방식 싼 값에 주식을 사고 비싼 값에 팔면 가장 이득을 볼 수 있다는 당연한 사실을 통해 주어진 주가를 역으로 탐색해 현재 가장 큰 값보다 비싼 값을 만날 때까지 이전의 모든 주식을 산 후에 팔아주면 된다. 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로 끝..

문제 접근 방식 문제 자체는 14501번 퇴사 문제와 똑같지만 입력의 양이 최대 150만 개이기 때문에 이전에 풀었던 방식처럼 O(n^2)의 시간 복잡도로 풀면 시간 초과가 발생한다. DP 테이블을 좀 더 효율적으로 채워 넣어야 시간 제한을 맞출 수 있으니 문제를 좀 더 자세하게 분석해보겠다. 우선 i번째 날에 t일의 시간이 소요되는 상담을 진행했다면 i + 1일에 p만큼의 돈을 지급받는다. 즉, i일 이전에 받은 돈들은 모두 정해진 기한 내에 완료하여 받을 수 있는 돈이고 i일에 받을 수 있는 가장 큰돈은 i일 이전의 값들 중 가장 큰 값이다. n 10 t p 5 50 4 40 3 30 2 20 1 10 1 10 2 20 3 30 4 40 5 50 위와 같은 테스트 케이스가 주어졌을 때 1일 2일 3일..

문제 접근 방식 문제에 나와 있는 예시를 살펴보면 4일의 경우에는 1일과 3일 중 하나를 선택할 수 있고 둘 중 더 큰 값을 선택하는 것이 효율적이니 더 큰 값을 골라주면 된다. (예시에서 두 날의 값은 같아서 뭘 고르든 상관은 없다.) 즉, 현재 날을 기준으로 이전에 상담이 끝나는 요일들 중 가장 비용이 큰 값을 선택해주면 된다. DP 테이블은 아래와 같이 정의했다. dp[i] = i번째 날에 받을 수 있는 누적 금액 dp[i] = 1 ~ i-1까지의 날짜 중 i일 이전에 끝나고 가장 비용이 큰 값 위의 과정을 코드로 작성하면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedRead..

문제 접근 방식 각 변의 길이가 1인 정삼각형으로 시작해 n번째 정삼각형의 한 변의 길이를 구해야 한다. 삼각형을 위와 같이 나선 모양으로 회전하면서 추가할 때 위와 같이 한 변의 길이가 이전 변의 길이보다 커질 때 새로운 삼각형을 추가해주고 이 때 새로운 정삼각형의 새로운 한 변의 길이는 dp[i] = dp[i - 1] + dp[i - 5]라는 것을 알 수 있다. dp[i-5]를 계산하기 위해 dp 테이블의 dp[1] ~ dp[5]까지를 각각 순서대로 1, 1, 1, 2, 2로 초기화 해준 후에 dp[6] ~ dp[n]까지 구한 공식대로 계산해주면 된다. 계산하다 보면 인트형의 범위를 벗어나니 long 타입으로 저장해줘야 한다. 풀이 public class Main { public static void..

문제 접근 방식 수열 {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이 주어졌을 때 1, 100, 2, 60, 50 처럼 들쑥날쑥한 부분 수열이 아닌 1, 2, 50, 60 처럼 증가하는 부분 수열 중에서 합이 가장 큰 부분 수열을 구해야 하는 문제다. 우선 간단하게 생각해보면 이전 수보다 큰 값이 나올 때까지 모두 합해주면 특정 수로 끝나는 부분 수열의 합을 구할 수는 있다. 1로 끝나는 부분 수열은 {1} = 1 1 > 100 > 2 (이전 수인 100보다 작음) == 100으로 끝나는 부분 수열은 {1, 100} = 101 2 > 50 > 60 > 3 (이전 수인 60보다 작음) == 60으로 끝나는 부분 수열은 {2, 50, 60} = 112 위와 같이 특정 수로 끝나는 부분 수열..