파게로그

문제 링크: 11053번 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 당분간 LIS 문제를 자주 접할 듯한데 정말 쉽지만은 않다고 생각된다. 이 문제의 경우 가장 긴 증가하는 부분 수열의 길이만을 알면 되므로, arr[i]보다 작은 arr[j] 중 최대인 dp[j]에 1을 더해주면 arr[i]를 포함하는 LIS의 길이가 나온다. 다만 arr[i]가 포함되지 않은 수열이 LIS일 수 있기에 dp를 모두 저장한 후 최종 출력 시 다시 한 번 최댓값을 찾아야 한다. 이는 O(n^2)의 알고리즘인데 보다 효율적인 알고리즘은 스스로의 힘으로는 힘들 것 같아 찾아서 익히고 구현해보도록 해야겠다. import java.io.BufferedReader; import ..

문제 링크: 2156번 제목 https://www.acmicpc.net/problem/2156 "연속으로 놓여 있는 3잔을 모두 마실 수는 없다"라는 조건에서 헤맸다. 내가 생각했던 것은, dp 배열이 이전의 정보를 담고 있는다는 것이었다. 즉 현재의 잔을 마셨을 때, 1번째 전 잔을 마셨을 때, 2번째 전 잔을 마셨을 때를 모두 나누어 생각해보고자 했다. 하지만 이러한 방법은 배열의 중간중간이 비게 되어 바람직하지 못하다. 어떤 잔을 마셨건 이를 저장할 필요없이 이러한 각각의 경우를 36라인과 같이 특정 시점까지의 잔 수를 dp[i-n]으로 살펴본 후 2번째 전 잔까지를 arr[i]로 별도로 더해주면 된다. package baekjoon.problem11053; import java.util.Scann..

문제 링크: 프로그래머스 Lv.2 기능개발 https://programmers.co.kr/learn/courses/30/lessons/42586 먼저 progresses를 배포까지 걸리는 날짜를 담고 있는 리스트로 바꾸어준다. 아직 배포되지 않은 기능들 중 가장 긴 기간을 long이라 하면, long이 progresses[i]보다 크거나 같으면 후자는 전자의 개발이 완료될 때까지 기다려야 한다. 반면 long이 progresses[i]보다 작으면 지금까지의 배포는 모두 완료되어야 한다. def solution(progresses, speeds): # 배포까지 남은 날짜로 변환 for i in range(len(progresses)): remainProg = 100 - progresses[i] remain..

문제 링크: 10844번 쉬운 계단 수 https://www.acmicpc.net/problem/10844 가장 마지막 자리인 mem[1]부터 시작해서 가장 첫 자리인 mem[n]까지 숫자를 붙여나가면서, mem[i]에는 가능한 경우의 수를 저장한다. n=1일 때를 제외하고는 mem[1][digit]에는, 아직 아무것도 정해지지 않은 상태이므로 반드시 1이 들어가야 한다. import java.util.Arrays; import java.util.Scanner; public class Main { static long[][] mem; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt..

문제 링크: 1463번 1로 만들기 https://www.acmicpc.net/problem/1463 예를들어, 9는 '27을 3으로 나눈다'는 한 번의 수행 또는 '10에서 1을 뺀다'는 한 번의 수행을 통해 만들어진다. 이를 통해 점화식을 세우면 다음과 같다. a[n] = min(a[n/3], a[n/2], a[n-1]) + 1 다만 a[n/3]과 a[n/2]는 나누어떨어지지 않는 경우 구할 수 없기에 divBy3, divBy2를 미리 선언하여 i가 3 또는 2로 나누어떨어지지 않을 경우 최댓값을 저장하도록 하여 min()에서 고려되지 않도록 한다. import java.util.Scanner; import java.util.Arrays; class Main { static int[] arr; pub..

문제 링크: 2579번 계단 오르기 https://www.acmicpc.net/problem/2579 s(n) = max( s(n - 2) + a(n), s(n - 3) + a(n - 1) + a(n) )의 식을 이용할 수 있다. 3개 계단을 연속해서 밟으면 안 된다는 조건을 고려해서, s(n -1)을 이용하지 않는 데에 초점을 두는 것이다. C/CPP #include #define MAX(a, b) ((a) > (b) ? (a) : (b)) int n, a[300], d[300]; int main(void) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &(a[i])); d[0] = a[0], d[1] = a[0] + a[1], d[2] = M..

문제 링크: 1932번 정수 삼각형 https://www.acmicpc.net/problem/1932 아랫층의 수는 윗층의 수 중 왼쪽 대각선과 오른쪽 대각선의 수만 고를 수 있다. 그리고 이것이 배열로 들어올 때는 아랫층 수가 a[row][col]이라면 왼쪽 대각선의 수는 a[row][col-1], 오른쪽 대각선의 수는 a[row][col]이다. 위에서부터 아래로 내려오면서, 윗층의 수 중 큰 것과 아랫층의 수를 더해서 저장하면 된다. 구현을 편리하게 하기 위해 triangle의 폭을 n+2로 선언하고 값을 입력받기 전 triangle을 -1(또는 0)로 초기화해두면 반드시 triangle 내의 숫자만 고려되기 때문에 왼쪽 끝과 오른쪽 끝을 신경쓸 필요가 없다. C/CPP #include #define..

문제 링크: 1149번 RGB거리 https://www.acmicpc.net/problem/1149 DP 문제이다. 연속된 집은 같은 색깔로 칠할 수 없으므로, i번째 집까지의 최솟값 mem[i] 중에서도 i번째 집이 RED일 때의 최솟값 mem[i][RED]는, i-1번째 집까지의 최솟값 mem[i-1] 중에서도 i-1번째 집이 GREEN일 때의 최솟값(mem[i][GREEN])과 i-1번째 집이 BLUE일 때의 최솟값(mem[i][BLUE])에 i번째 집을 RED로 칠할 때의 비용(arr[i])을 더한 것이다. 이처럼 mem[i]는 i번째 집의 색깔에 따라 세 개의 값을 저장하고 있어야 한다. import java.util.Scanner; public class Main { static int RED..