Java/Algorithms

문제 접근 방식 문제 자체는 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 위와 같이 특정 수로 끝나는 부분 수열..

문제 접근 방식 어떻게 풀어야할지 모르겠어서 일단 각 자리수별로 만들 수 있는 경우들을 직접 나열해보고서 규칙을 찾아보았다. 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010 1000000 1000001 1000010 1000100 1000101 1001000 1001001 1001010 1010000 1010001 1010010 1010100 1010101 각 자리수별로 경우의 수를 세어보면 1, 1, 2, 3, 5, 8, 13, ... 이런식으로 증가하는 것을 알 수 있는데 어디서 많이 본거 같다면 생각하는 그 피보나치 수열이 맞다. 1과 2의 경우..

문제 접근 방식 기존 1로 만들기 문제에 1이 되는 순서까지 출력하는게 추가된 문제기에 기존 DP 테이블 외에도 순서를 기록할 배열을 더 만들어서 기록해주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] dp = new int[n + 1]; int[] history = new int[n + 1]; for (int i = 2; i dp[i/2] + 1) { dp[i] = dp[i/2] ..

문제 접근 방식 Prefix Sum 알고리즘을 사용해 풀 수 있는 문제로 i ~ j까지의 구간합은 (i 까지의 합) - (j-1까지의 합)이라는 공식을 이용해 DP 테이블에는 i까지의 합들을 저장하고 위의 공식대로 계산해주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Inte..

문제 접근 방식 11726번 문제에서 2*2 타일의 경우가 추가된 문제다. i번째에 놓을 수 있는 경우가 기존 문제에서는 DP[i-1] + DP[i-2] 였다면 이번 문제에서는 DP[i-2]를 한 번 더 더해주면 된다. DP[i-2]를 한 번 더 더해주는 이유는 이전 문제 설명글에서 설명한거처럼 1*2 타일을 놓는 경우는 나머지 한층도 1*2 타일을 놓을 수 밖에 없어 사실상 2*2타일을 놓는 경우와 같기 때문에 해당 경우를 한 번 더 계산해 주기만 하면 된다. 따라서 DP 테이블의 초기값은 기존 문제의 테이블에서 2번째 경우에 한 가지를 더 추가해서 DP[1] = 1, DP[2] = 3이 되고 이 테이블을 기준으로 계산해주면 된다. 풀이 public class Main { public static vo..