ezhoon

📖 문제 백준 1912 ⚠️ 주의사항 첫 번째 칸과 마지막칸은 필수 연속된 세 개의 계단을 모두 밟아서는 안된다 단 시작 계단은 제외 ✍️ 이해 /** * 세칸 연속으로 갈 수 없다는 점 생각하면서 점화식 짜보기 * * 2칸 전의 dp값 || 3칸 전의 dp + 한 칸 전의 값(3칸 전의 dp값이므로 2번째 값을 안사용 했다는 의미 -> 바로 전 값을 사용할 수 있다.) * 위 내용을 점화식으로 쓰면 아래와 같다. * Math.Max(dp[i-2], dp[i-3] + arr[i-1]) + arr[i] (더 큰 값에 현재 값 더하기) * * 표로 그리자면 아래와 같다. * * 10 20 15 25 10 20 * N 0 1 2 3 4 5 6 * dp 0 10 30 35 50 65 65 * dp 0 0 20 ..

📖 문제 백준 1912 ⚠️ 주의사항 중간에 음수가 들어갈지라도 최댓값이 될 수도 있다. 0 1 2 3 4 5 6 7 8 9 2 1 -4 3 4 -4 6 5 -5 1 위 표에서 최댓값은 index 3~7사이의 합이다. 즉 음수 양수 상관없이 생각해야한다. ✍️ 이해 /** * 1. dp 식 찾기 * dp[i] = Math.max(dp[i-1] + arr[i], arr[i]) * 2. 즉 이전까지의 합 + 현재 arr을 더한것과 / 현재 arr만 비교 해서 더 높은 것을 dp에 저장 * 3. max에 현재 dp값과 max값 비교 */ ✏️ 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader..

📖 문제 백준 11054 ⚠️ 주의사항 LIS 알고리즘을 적용해서 풀어야 한다. 증가하는 경우 감소하는 경우 2가지의 경우를 인지할 것 ✍️ 이해 ** * 1. LIS(Longes Increasing Subsequence) 알고리즘 이용 * 2. 증가하는 경우 / 감소하는 경우 즉 -> 오른쪽 : 1, 2, 4, 5 * 오른쪽->왼쪽 : 5, 2, 1 * 즉 5가 겹치게 되기에 이때문에 1을 빼줘야 한다. */ ✏️ 풀이 public class Main { static int N; static int[] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); arr = new in..

📖 문제 백준 11722 가장 긴 감소하는 부분 수열 ⚠️ 주의사항 이전 11053에서 if문만 바뀐 형태 2022.05.03 - [[Java] 백준 문제풀이/DP] - [백준] 11053 가장 긴 증가하는 부분 수열_Java ✏️ 풀이 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int max = 1; int[] arr = new int[N + 1]; int[] dp = new int[N + 1]; for(int i=1; i

📖 문제 백준 11053 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ⚠️ 주의사항 부분 수열이므로 경우의 수를 유심히 생각해봐야함 i 0 1 2 3 4 5 6 7 8 Arr[] 0 3 5 7 9 2 1 4 8 DP[](길이) 0 1 2 3 4 1 1 2 4 i = 8 일때 DP의 값(부분 수열의 길이)이 4인 것을 볼 수 있다. 부분 수열을 모를 경우 3이라고 생각할 수 있지만 i가 8일때 값을 적어..

📖 문제 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net ⚠️ 주의사항 4개의 포도주가 있다고 가정한다. 12, 21, 25, 1로 이루어져 있을 경우 누적 최댓값은 아래와 같다. 21 + 25 = 46 (최대) 12 + 25 + 1 = 38 무조건 3개를 더한다고 높은 값이 나오는게 아니라는 점을 유의해야 한다. 즉 마지막 와인이 선택 될 때가 최대 누적합일수도 있고, 그 이전 와인잔까지 선택이 누적합일 수도 있다. ✍️ 이해 /** * 점화식 만들기 전 주의 사항 * - 4개의 포도주가 있다고 ..

📖 문제 백준_2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net ⚠️ 주의사항 문제의 규칙 찾기 ✍️ 이해 /** * 1 : 1개 [1] * 2 : 1개 [10] * 3 : 2개 [101, 100] * 4 : 3개 [1010, 1001, 1000] * 5 : 5개 [10101, 10100, 10010, 10001, 10000] * 피보나치 규칙 이용 * dp[n] = dp[n-2] + dp[n-1] */ ✏️ 풀이 import java.io.BufferedReader; import java...

📖 문제 백준_11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net ⚠️ 주의사항 앞자리의 수가 0,1을 제외한 나머지 수가 불가능 -> 2나 9가 들어오면 91,21이 돼 오르막수가 되지 못함 ✍️ 이해 /** * 1. 이전에 문 계단수와 비슷한 유형의 문제 * 2. 반복문 스타일 * 3. 0~9까지의 숫자에서 만들 수 있는 오르막수는 이전 자릿수 N-1 에서의 j부터 마지막 9까지의 합을 구해야 함 */ ✏️ 풀이 public class Main { public st..

📖 문제 백준 10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ⚠️ 주의사항 0으로 시작하는 경우는 없다. 0 혹은 9로 끝나는 경우는 각각 1과 8로만 파생된다. ✍️ 이해 /** * 1. 인접한 모든 자릿수가 1씩 차이나지만 0은 1로 9은 8로 하나씩만 파생이된다. * 2. 단 0으로 시작하는 경우는 없기에 처음에 선언 할 때 0은 제외 할 것 * 3. 점화식 : dp[n][i] = dp [n-1][i-1] + dp [n-1][i+1] * 4. 재귀 방식으로 풀이 * 5. 메모이제이션 사용 */ 4번 메모이제이션을 처음에는 적용하지 않아 시간 초과가 계속 떴다. ✏️ 풀이 import java.io.Buffe..

📖 문제 백준 9059 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ⚠️ 주의사항 같은 조합의 경우에도 다른 순서면 다른 조합으로 생각해야 한다. ✍️ 이해 /** * 4를 예시로 들면 1+2+1, 2+1+1, 1+1+2 이런 식으로 순서만 달라도 다른 경우의 수로 생각 * 합이 입력한 값이 될 때까지 1,2,3 각각 더하고 만약 누적된 값이 입력값 보다 높으면 answer 누적 안하고 return 해서 스택 pop하기 */ ✏️ 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; pu..