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] 백준 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 사각형을 채우는 경우의 수는..

[JAVA] 백준 1463번 【1로 만들기】

Dynamic Programing을 사용하는 문제이다. 먼저, 메모이제이션 해둘 dp[ ] 배열을 생성한다. dp[n]의 의미는 n에서 1로 변환할때 드는 최소의 연산수를 저장할 것이다. 먼저 dp[0] 과 dp[1] 의 값이 0 임은 명확한 사실이고, dp[2]부터 조건문을 이용해 정의를 한다. 2를 1로 만드는 횟수의 최솟값은 무엇일까. 먼저 2가지 연산을 진행할 수 있다. 1을 빼거나, 2를 나누는 것 2-1 = 1 이므로 dp[2]=dp[1]+1=0+1=1 2/2=1 역시, dp[2]=dp[1]+1=0+1=1이다. 둘다 값이 1이므로 두 연산의 최솟값은 1이다. 2에서 1로 만드는 연산의 최솟값은 1이므로, dp[2]=1을 기록한다. 3을 1로 만드는 횟수의 최솟값은? 3은 1을 빼거나 3을 나누..