꾸준히 삽질하기,,

✴️ 문제https://school.programmers.co.kr/learn/courses/30/lessons/12913 ✴️ 문제 풀이 `dp[i][j]`에는 i행 j열 선택했을 때까지의 점수의 최대값을 담고잇다. `dp[2][1]` 의 경우를 생각해보면 `(2,1)`까지의 최대값으로 1열을 지나가는 경우이기 때문에 `(1, 1)`은 지나갈 수 없다.그렇다면 `dp[2][1]`에 들어갈 값을 생각해보면 `dp[1][0]`, `dp[1][2]`, `dp[1][3]` 을 지나고` land[2][1]`을 지나가는 경로 중 점수가 최대인 값이 들어가야 할 것이다. 마지막 행은 해당 지점을 종착지로하는 점수의 최대값을 담고있기 때문에 행의 모든 값 중 최대값을 구하면 그게 `answer`가 된다. ✴️ 전체 ..

📍 문제 https://www.acmicpc.net/problem/11722 📍 문제 풀이 이 문제에서 유의해야할 점은 두가지이다.감소하는 수열은 연속되지 않아도 된다감소하는 수열의 초기값은 1이다 (본인을 포함해야하기 때문에)`dp[i]`에는 가장 긴 수열의 길이를 저장하고`nums[0]` ~ `nums[i-1]` 까지의 수 중에 `nums[i]`보다 큰 수를 찾아 해당 `수열의 길이에 + 1`을 해주는 과정을 반복한다.만약 존재하지 않는다면 자기 자신으로만 이루어진 수열이 가장 긴 수열이 될 것이다 문제에서 주어진 예를 가지고 살펴보면 i = 0자기 자신만 포함하는 수열이 가장 긴 수열이기 때문에 `dp[0] = 1`i = 1이전의 수 중 30보다 큰 수는 없기 때문에 {10} 또는 {30}이 감..

📍 문제 https://www.acmicpc.net/problem/1912 📍 문제 풀이dp[i]는 i까지의 연속합의 최대값을 의미한다.(dp 문제의 경우에는 지금 값을 선택하냐 하지 않냐의 경우로 경우를 나눠서 값을 지정하는 경우가 대부분) 연속적인 값들의 합을 구하는 방법은 아래 두가지이다.이전까지의 연속합에 현재 값을 더하는 경우dp[i] = dp[i-1] + nums[i]현재값으로 초기화 해주는 경우dp[i] = nums[i] 즉, 모든 경우에서 연속합이 최대가 되는 경우를 찾기 위해서는 1과 2 둘 중 최대값을 찾으면 된다dp[i] = Math.max(dp[i-1] + nums[i], nums[i]) 예를 들어 살펴보면 아래와 같다.계속해서 `nums[i]`와 `dp[i-1] + nums[i..

📍 문제 https://www.acmicpc.net/problem/2579📍 문제 풀이우선 계단을 올라갈 수 있는 방법이 두 가지 있다. `n-3`을 밟고 `n-1`을 밟는 방법`n-2`를 밟는 방법연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.는 조건때문에 이외의 경우는 존재하지 않는다.dp 배열을 통해서 위의 두 방식 중 최대 값을 구해가며 dp 배열을 완성해주면 풀 수 있다. 하지만, 런타임에러가 계속 떠서 좀 헤맸다문제에는 계단의 갯수는 자연수라는 조건이 있다,,,즉, n이 1인 경우에 대해서 아래 코드를 실행했으니 계속에서 런타임 에러가 나는 부분이었다,,다들 조건 잘 확인하시길,,dp[0] = 0;dp[1] = stair[1];dp[2] = stai..

📍 문제https://www.acmicpc.net/problem/10844 📍 문제 풀이 dp[n][i]를 i로 시작하는 길이가 n인 계단수의 갯수를 의미한다.i로 시작하는 수를 적으면 아래와 같고 dp배열에는 값들의 갯수가 들어가야 한다.   예를 들어 dp[2][4]를 살펴보자.dp[2][4]는 4로 시작하는 길이가 2인 계단수의 갯수를 의미한다.4로 시작하는 경우 일의 자리에 올 수 있는 경우는 3 혹은 5뿐이다.이는 dp[1][3]과 dp[1][5]를 의미함을 알 수 있을 것이다.즉, dp[2][4] = dp[1][3] + dp[1][5]로 나타낼 수 있다. 그렇다면 세자리 숫자는 어떻게 될지 생각해보면dp[3][5]의 경우 5로 시작하는 길이가 3인 계단수의 갯수이다.5로 시작하는 경우 그 ..

📍 문제https://www.acmicpc.net/problem/1699 📍 문제 풀이 dp배열은 제곱수로 나타냈을 때 최소 항의 갯수를 의미한다.그렇기 때문에 제곱수의 dp값은 반드시 1이다. 항의 최소 갯수를 만들기 위해서는 현재값보다 작지만 가장 큰 제곱수를 찾아야한다.예를 들어,  13보다 작지만 가장 큰 제곱수는 921보다 작지만 가장 큰 제곱수는 16 13을 예를 들어 생각해보면 13보다 작은 제곱수는 1, 4, 9이다.즉, dp[1] = dp[4] = dp[9] = 1이다. 13 = ( 9 + 4 ) = ( 9 + 1 + 1 + 1 )즉, 제곱수끼리의 합으로 나타낼 수 있을 때, 최소 갯수를 가진다. 📍 전체 코드import java.util.Scanner;public class boj..

📍 문제 https://www.acmicpc.net/problem/12738 📍 문제 풀이이분탐색으로 풀이한다입력받은 값을 `nums`에 넣어주고 `nums[0]`을 list에 넣어준다그리고 `result`의 마지막 값보다 배열의 값이 클 경우 증가하는 수열이 성립하므로 `result`에 추가해준다아닌 경우에는 해당 값이 `result`에 들어갈 위치를 찾는다  -> 이 부분이 이분탐색 `result`에서 들어 갈 위치를 찾는거니깐 아래와 같이 `start`와 `end`를 지정해줬다.int start = 0;int end = result.size() - 1; `result[idx]`의 값이 `nums`의 값보다 같거나 큰 경우 그 위치에 넣어주는 방식으로 진행했다. 풀고나서 다른분들의 풀이를 좀 살펴..

📍 문제 https://www.acmicpc.net/problem/9465  📍 문제 풀이 dp[i][j] 는 dp[0][0] ~ dp[i][j]까지 스티커를 떼었을 때 얻을 수 있는 최대 점수 `dp[0][1]`은 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없다는 조건에 의해 `dp[1][0] + dp[0][1]`의 최대값을 가진다.`dp[1][1]`도 같은 조건에 의해 `dp[0][0] + dp[1][1]`의 값을 가진다. `dp[0][2]`의 경우에는 `dp[1][0]`과 `dp[1][1]` 중 더 큰 값을 구해야 한다. 더 일반적인 경우를 확인하기 위해서 `dp[0][3]`를 살펴보면이전자리의 스티커를 떼었을 수도 있고, 떼지 않고 건너뛰었을 수도 있다.  두가지 경우 중 최대 점수..

📍 문제 https://www.acmicpc.net/problem/2629 📍 문제 풀이  주어진 추의 무게로 구슬의 무게를 확인할 수 있는가의 문제이다무게를 확인해야하는 구슬을 한쪽으로 고정 -> 왼쪽그렇다면 경우의 수는 3가지더보기1. 구슬을 왼쪽에 추가2. 구슬을 오른쪽에 추가3. 구슬을 올리지 않음일종의 0-1 배낭문제이다.배낭문제의 경우에는 Max가 주어지고 그 안에서 그 한도내에서 넣을 수 있는 최대값을 골라내는 문제라면 이 문제의 경우에는 모든 숫자 조합을 저장해주면 된다.  🙋🏻 재귀 이용static void getWeights(int num, int weight) { if(dp[num][weight]) return; dp[num][weight] = true; if(num ==..