Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처RGB 거리 실버 1 📖 문제 DP 문제로현재 집 비용 + 이전 집에서 현재 집 열이 아닌 2 곳 중 가장 적은 비용을 가진다. 점화식을 세워보면 이렇다. dp[i][j] = Math.min(dp[i][j+1], dp[i][j+2]) + house[i][j];물론 한 행에 집은 3개이므로 현재 열을 제외한 다른 집 중에서 가장 적은 비용을 선택하므로% 연산이나 if문을 써서 현재 집 열을 피하면 된다.   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ..

✔️ 출처쉬운 계단 수 실버 1 📖 문제중복 연산이 많이 일어나고 반복적이다.  이참에 다시 학교에서 배운 DP의 적용 요건을 복습하겠다.  최적 부분구조(Optimal substructure)큰 문제의 최적 해에 하위 문제의 최적 해가 포함하위 문제들의 중복 (overlapping recursive calls)재귀적 해법으로 풀면 같은 하위 문제에 대한 호출이 심하게 중복 재귀적으로 깊이만큼 0~9까지 +1 -1을 하면서 생성하다보면 엄청난 중복이 생김이전의 깊이에서 얻은 갯수를 재활용할 수 있을 것 같음. DP를 적용해보자 우선 0과 9는 1가지 밖에 없다.0 → 19 → 8따라서 0 과 9는 따로 처리하고 1~8까지는 -1 +1 숫자가 계단 수이니 이전 깊이의 -1 +1 숫자의 개수를 더한다.  ..

🧫 문제 분석✔️ 출처회의실 배정 실버 1 📖 문제 정렬 문제로 회의가 끝나는 시간을 기준으로 정렬하되 같다면 시작시간을 오름차순으로 정렬해야한다.주의할 점은 끝나는 시간에 바로 다른 회의가 시작할 수 있다는 것이다.  정렬 후 마지막 회의 시간 보다 다음 회의의 시작시간이 크거나 같으면 이는 가능한 회의이므로 마지막 회의시간을 다음 회의가 끝나는 시간으로 바꾼다.   종료시간이 같다면 시작시간을 오름차순 정렬을 해야하는 이유예를 들어보면41 22 24 42 4 이것을 끝나는 시간으로만 정렬했을 경우입력 순서대로 1 22 24 42 4 이대로 들어왔을 것이고 마지막 회의시간은 2 -> 2-> 4로 되고 2 4 일때 마지막 회의시간 = 4 이기에 이 회의는 무시된다. 따라서 잘못된 답을 내놓게 ..

🧫 문제 분석 ✔️ 출처포도주 시식 실버 1 📖 문제 동적 프로그래밍 문제이다.  문제를 보면1. 선택한 잔은 모두 마시고 원위치2. 연속으로 3잔 마시기 불가능 i = 3 부터 시작 1. 현재 잔 + dp[i - 2]2. 현재 잔 + 이전 잔 + dp[i - 3]3. dp[i - 1]    // 이전까지의 최댓값을 가진다.  이 세가지 중 max값을 찾으면 된다.    1. 현재 잔 + dp[i - 2]2잔을 마시고 한 칸 뛰고 한 잔을 마신 경우이다.  1 2 3 번째 잔을 연속해서 마실 수 없으므로 dp[1]의 값 즉, 0과 1 번째 잔을 마신 최댓값 을 더한다.  2. 현재 잔 + 이전 잔 + dp[i - 3] 한 잔을 마시고 한 칸 뛰고 연속으로 2잔을 마신 경우이다.dp[0] 잔까지 마시고..

🧫 문제 분석 ✔️ 출처Z 실버 1 📖 문제  문제에서 답을 줬다.  n-1 크기로 4등분 배열을 4 등분 하면서 구역을 4구역으로 나눈다.  (r,c) 의 위치가 어느 구역인지 판별후 해당 구역의 이전 구역들의 방문 수를 더하면서 n == 1 일때가지 진행한다.  내가 짠 코드는 문제에서 n-1 크기로 줄여가며 4등분하는 것을 활용해서 했더니 다른 사람들과 차이가 난다. 좀 복잡하게 풀었다.   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int[][] arr; static int r; static int c; static int count = 0; public static void main..

🧫 문제 분석 ✔️ 출처봄버맨 실버 1 📖 문제 그래프를 써야할것 같은 느낌이 솔솔 느껴진다.그러나 DFS / BFS 문제는 아니다. 문제에서 '연쇄 반응이 없다' 하였다. 문제 실행 단계0. 초기상태 (폭탄이 미리 심어져있음)1. 아무것도 안한다.2. 모든칸에 폭탄 설치3. 3초전 설치된 폭탄 모두 폭파  4. 2번 부터 반복  초로 예시를 보면  0초 : 초기 상태1초 : 아무것도 안함2초 : 모든 칸에 폭탄 설치3초 : 3초전에 설치된 폭탄 모두 폭파 (0초 때 설치한 폭탄들)         - 이때 폭파되지 않은 부분이 다음 초기상태 (0초때 설치한 폭탄들)가 된다.4초 : 모든 칸에 폭탄 설치5초 : 3초전 설치된 폭탄 모두 폭파    0 과 1로 폭탄을 구분하여 설명하자면먼저 0초때에 초기..