👨🏻‍💻 PS

[JAVA] 백준 1699번 【제곱수의 합】

이 문제를 처음에, 단순하게 특정 숫자와 가장 가까운 제곱수를 구하고, 특정 숫자와 제곱수의 차이에 해당하는 dp값을 더하는 방식으로 접근을 했었다. 예를 들어, 초기값으로 dp[1]= 1, dp[2]=2(1+1이므로 2개) , dp[3]=3(1+1+1 이므로 3개) 를 설정한 뒤, 만약 18이라면, 18과 가장 가까운 제곱수는 16이기 때문에, dp[18]=1(16이므로 갯수 하나 소요)+dp[2] 와 같은 방식으로 말이다. 즉, 이와 같은 방식을 사용하면 18 = 4의 제곱 + 1의 제곱 + 1의제곱 = 총 갯수 3개가 나오는데, 사실 18 = 3의제곱 + 3의제곱 = 2개 가 더 최소갯수이다. 그래서, 다른 방법으로 다시 접근해야 했다. 먼저, 특정 숫자에서 제곱수를 추출하는 것은 필수적이다. 하지..

[JAVA] 백준 2579번 【계단 오르기】

[JAVA] 백준 2156번 【포도주 시식】 포도주가 문제에 나와있는 예제처럼 있다고 가정해보자. Dp[n]은 해당 n번째 까지, 포도주를 최대로 마신 량을 기록할 것이다. Dp[1] 은 당연하게도 wine[1]이다. 1잔 밖에 없으니, 1잔을 마신게 최대 yinq.tistory.com 계단 오르기 문제는 2156 포도주 시식과 비슷한 문제라고 볼 수 있다. 어쩌면 더 쉬운 문제이다. 포도주 시식 문제의 경우 마지막 잔을 꼭 마셔야 한다는 조건은 없지만, 계단오르기 문제는 마지막 계단은 꼭 밟아야 한다는 조건이 있다. dp배열에 각 계단 위치에 올랐을 때, 얻을 수 있는 점수의 최댓값을 기록할 것이다. 마지막 계단은 꼭 밟아야 한다는 조건 때문에, dp[i]값에는 array[i]값은 무조건 포함이 되어야..

[JAVA] 백준 1912번 【연속합】

이제 부분수열 구하는 문제는 해답이 잘 나오는 것 같다. 이 문제는, 누적합이 -값이 되지 않는한 게속해서 더해서 dp값에 저장하고, 음수가 되면 어떤수를 더해도, 안더하는게 이익인 상황이 되기 때문에, 누적합이 음수가 되는 해당 인덱스의 dp값을 0으로 입력시키게끔 구현하였다. 예제문제를 통해 살펴보도록 하자. 최종 dp배열은 위와 같이 생성되고, dp배열에서 가장 큰 원소를 추출하면 끝난다! 그리고 모든 원소가 0보다 작은 경우, 누적합의 최댓값은 원래 배열의 음수 원소들 중 가장 큰값이 된다. 이 부분에 유의하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import j..

[JAVA] 백준 11054번 【가장 긴 바이토닉 부분 수열】

바이토닉 부분수열의 길이를 구하기 위해서는, 어떤 인덱스에 위치한 수를 기준으로 앞에서부터 시작하는 가장 긴 증가하는 부분수열의 길이와 뒤에서부터 시작하는 가장 긴 부분수열의 길이를 알아야겠다 생각이 들었다. [JAVA] 백준 11053번 【가장 긴 증가하는 부분 수열】 dp 배열을 생성하여 dp[i] 는 Array[i]까지의 원소들로 만들 수 있는 부분 수열 길이의 최댓값을 입력할 것이다. 그리고 부분 수열의 길이는 최소 1 값을 가지므로, dp의 모든 원소는 디폴트 1을 가진 yinq.tistory.com 원리는 위 문제와 동일하다. 대신 앞에서 부터 시작하는 증가 부분수열을 기록해놓을 dpAsc배열과 뒤에서 부터 시작하는 증가 부분수열을 기록해놓을 dpDsc 두개의 dp배열을 생성하였다. 그리고 d..

[JAVA] 백준 11722번 【가장 긴 감소하는 부분 수열】

[JAVA] 백준 11053번 【가장 긴 증가하는 부분 수열】 dp 배열을 생성하여 dp[i] 는 Array[i]까지의 원소들로 만들 수 있는 부분 수열 길이의 최댓값을 입력할 것이다. 그리고 부분 수열의 길이는 최소 1 값을 가지므로, dp의 모든 원소는 디폴트 1을 가진 yinq.tistory.com 가장 긴 증가하는 부분 수열에서 조건을 Array[i]

[JAVA] 백준 11055번 【가장 큰 증가 부분 수열】

dp 배열을 생성하고 dp[i]에는 i 번째 원소가 형성하고 있는 부분 수열의 합을 넣을 것이다. 즉, dp[i] 는 수열의 i번째 원소까지 가장 큰 부분수열의 합을 기록할 것이다. 예를 들면 A = [1 2 3 10 5 14] 가 있다고 할때 dp = [1 3(1+2) 6(1+2+3) 16(1+2+3+10) 11(1+2+3+5) 30(1+2+3+10+14)] = [1 3 6 11 16 30] 이 되는 것이다. 여기서 중점적으로 봐야할 포인트는, dp[5]를 구할때이다. 부분 수열의 경우의 수가 2가지 존재한다. [1 2 3 5 14 ] 즉, 총합이 25가 되는 경우와 [1 2 3 10 14] 즉, 총합이 30이 되는 경우의 수가 존재한다. 채우는 방법은, 30보다 작은 원소를 발견하면, 그 원소가 갖고..

[JAVA] 백준 11053번 【가장 긴 증가하는 부분 수열】

dp 배열을 생성하여 dp[i] 는 Array[i]까지의 원소들로 만들 수 있는 부분 수열 길이의 최댓값을 입력할 것이다. 그리고 부분 수열의 길이는 최소 1 값을 가지므로, dp의 모든 원소는 디폴트 1을 가진다는 사실은 알 수 있다. dp를 채우는 메커니즘을 알아보자. 위 그림과 같이, dp 6번째 원소를 채워야 하는 상황이라고 생각해보자. Array의 첫번째 원소 10은 40보다 작으므로, 부분수열의 길이는 10이 가진 dp값 1보다 1이 큰 2로 업데이트 할 수 있다. Array의 두번째 원소 20은 40보다 작으므로, 부분수열의 길이는 20이 가진 dp값 2보다 1이 큰 3으로 업데이트 할 수 있다. Array의 세번째 원소 30은 40보다 작으므로, 부분수열의 길이는 30이 가진 dp값 3보다..

[JAVA] 백준 2156번 【포도주 시식】

포도주가 문제에 나와있는 예제처럼 있다고 가정해보자. Dp[n]은 해당 n번째 까지, 포도주를 최대로 마신 량을 기록할 것이다. Dp[1] 은 당연하게도 wine[1]이다. 1잔 밖에 없으니, 1잔을 마신게 최대값이 된다. Dp[2] 역시 당연하게 wine[1]+wine[2] 가 된다. 연속으로 3잔을 마시는건 안되지만, 2잔을 마시는 건 허용이 된다. 그렇다면 Dp[3]은 어떻게 채울까 3가지 Case가 있을 수 있다. Case.1 이미 1번째 잔과 2번째 잔을 마신 경우 3번째 잔은 마실 수 없고 Dp[3]은 더 마신 와인이 없으니, 변화없이 wine[1] +wine[2] = 16이 될 것이다. Case.2 1번째 잔과 3번째 잔을 마실 경우, Dp[3]은 wine[1] + wine[3] = 19가 ..

[JAVA] 백준 9465번 【스티커】

점수표 Sticker 배열 S가 위와 같이 있다고 생각해보자. 그리고 Sticker 배열과 크기가 같은 Dp 배열이 있다고 생각해보자. Dp 배열은 해당 위치를 뜯었을 때, 얻을 수 있는 최대의 점수를 기록해 나갈 것이다. 먼저 Dp[0][1] 과 Dp[1][1]은 간단하다. 해당하는 부분을 뜯었을 때, 해당하는 점수만 획득할 수 있을 것이다. 그렇다면, 두번째 열부터는 점수가 어떻게 될까? 노란 바탕이 스티커를 뜯은 부분이라고 생각할때, S[0][2] 를 뜯었을 때 얻을 수 있는 최고 점수는, 상식적으로 하나만 뜯는것이 아닌, 인접하지 않은 S[1][1]까지 뜯은 점수의 합일 것이다. 즉 Dp는 해당 위치를 뜯었을 때 얻을 수 있는 최대 점수를 기록하는 것이기 때문에, 위와 같이 기록할 수 있다. 3번..

[JAVA] 백준 2193번 【이친수】

패턴을 파악하기 위해서 트리구조로 그려보았다. 그랬더니, 위와 같이 파악할 수 있었고, 피보나치 수열이구나 깨달았다. Dp[1] = 1 Dp[2] = 1 Dp[3] = 2 Dp[4] = 3 Dp[5] = 5 경우의 수를 적어보기만 했어도, 피보나치임을 예측했을 것 같다..ㅎㅎ 아무튼 Dp[i] = Dp[i-1]+Dp[i-2] 점화식을 사용하면 문제는 매우 간단하게 해결된다! import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); long [] Dp = new long[N+2]; Dp[..

[JAVA] 백준 11057번 【오르막 수】

패턴을 찾기 위해 경우의 수를 살펴보자. 0으로 시작하는 것도 허용하고, 00 이나 11 과 같이 같은 숫자가 연속된 경우에도 오름차순으로 간주하므로 위와 같은 경우의 수가 있을 수 있다. 이렇게 색을 칠하면 패턴이 보일 것이다. 즉 N자리 i로 시작하는 오르막 수는 N-1자리 i로 시작하는 오르막수부터 N-1자리 9로 시작하는 오르막수를 더하면 된다. Dp[i][j] = Dp[i-1][j] + ····· Dp[i-1][9] 위 식을 표현하면 되는데, 나는 for문을 3개 사용하여 표현하였다. for (int i = 2; i

[JAVA] 백준 10844번 【쉬운 계단 수】

먼저, 패턴을 찾기 위해 경우의 수를 살펴보자 0으로 시작하는 수도 경우의 수를 따져보았고, 결과를 출력할 때 더해주지만 않으면 문제가 없다. 메모이제이션을 위한, Dp[자릿수][시작하는수] 로 2차원 배열을 선언해준다. 0으로 시작하는 경우 3자리수로 만든 계단의 수를 살펴보면, 0으로 시작하는 수는 010 과 012 가 있다. 0을 때어놓고 보면, 10 과 12 임을 알 수 있고 0으로 시작하는 3자리 계단 수는 1로 시작하는 2자리 계단의 수임을 알 수 있다. 즉, 0으로 시작하는 N자리 계단 수는 1로 시작하는 N-1자리 계단의 수와 같다. Dp[N][0]=Dp[N-1][1] 9로 시작하는 경우 3자리수로 만든 계단의 수를 살펴보면, 9로 시작하는 수는 987 과 989가 있다. 9를 떼어놓고 보..

[JAVA] 백준 9095번 【1, 2, 3 더하기】

위와 같은 원리를 파악하면 쉽다. 4 = 3 +1 로 표현할 수 있고, 3을 표현하는 경우의 수는 이미 알고있다. 4 = 2 + 2 로 표현할 수 있고, 2를 표현하는 경우의 수는 이미 알고있다. 4= 1 + 3 로 표현할 수 있고, 1을 표현하는 경우의 수 역시 알고 있다. 즉, n일 때 n=(n-1) +1 n =(n-2) +2 n =(n-3) +3 로 표현할 수 있고 n을 표현하는 경우의 수는 n-1을 표현하는 경우의 수 + n-2을 표현하는 경우의 수 + n-3을 표현하는 경우의 수 임을 알 수 있다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Sc..

[JAVA] 백준 11727번 【2×n 타일링 2】

11726번 문제와 굉장히 유사하다. [JAVA] 백준 11726번 【2×n 타일링】 먼저, 문제의 원리를 이해해야한다. 다이나믹 프로그래밍 문제로, Dp[n] 은 2*n 사각형의 경우의 수를 메모이제이션 해야한다. 2*1 사각형의 경우 1가지, 2*2 사각형의 경우 2가지가 나온다. 위 그림 yinq.tistory.com 11726 번을 먼저 이해하는 것이 좋다. 차이점이라고 한다면, 2*2 사각형도 사용하여 채우기 때문에, 2*3 사각형 경우의 수에서, 2*1 사각형 경우의 수가 2번 있는 것과 같은 이치가 된다. 즉 Dp[n] = Dp[n-1] +2*Dp[n-2] 식으로 점화식을 구성하면 된다! import java.util.Scanner; public class Main { public stati..

[JAVA] 백준 11726번 【2×n 타일링】

먼저, 문제의 원리를 이해해야한다. 다이나믹 프로그래밍 문제로, Dp[n] 은 2*n 사각형의 경우의 수를 메모이제이션 해야한다. 2*1 사각형의 경우 1가지, 2*2 사각형의 경우 2가지가 나온다. 위 그림에 따라, 2*3 사각형을 생각해보면, 제일 오른쪽에 2*1 사각형을 추가하고나서 남은 2*2 사각형을 어떻게 채울지 고민해보면 되는데, 고민할 필요가 없다. 이미 2*2 사각형을 채우는 경우의 수를 알고있기 때문이다. 또한, 1*2 사각형 두개를 = 모양으로 놓고, 남은 2*1 사각형을 어떻게 채울지 고민해보면 되는데, 이 역시, 2*1 사각형을 채우는 경우의 수를 알고 있기 때문에, 더해주기만 하면된다. 즉, 피보나치 수열의 형태를 띄고 있음을 파악할 수 있다. 2*3 사각형을 채우는 경우의 수는..