전체 글

[PS] 백준 10844번 쉬운 계단 수 - DP

문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 dp[자릿수길이][마지막자릿수]로 이차원 배열을 사용하여 푼다. 이 풀이를 참고하였다. 0~9까지의 숫자를 사용할 수 있으나 0이 첫번째 자리에 오면 안된다. 따라서 길이가 1인 dp[1][1~9]의 값은 순서대로 1,2,3,4,5,6,7,8,9 로 경우의 수가 1개씩 밖에 없다. 길이가 1인 계단수의 총 개수는 9개가 된다. 1~9까지의 숫자의 경우, 계단 수 규칙에 따라 옆자리에 -1, +1인 수가 올 수 있다. (경우의 수가 2) 위 필기에서 나열된 dp[2][ ], dp[3][ ]의 경우의 수를 보면 알 수 있듯이 규칙성에 따라 도출되는 점화식 dp[n] = ..

[PS] 백준 9095번 1, 2, 3 더하기 - DP

문제 예제 풀이 점화식 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 를 사용하여 푼다. 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); Integer[] dp = new Integer[11]; dp[1] = 1; dp[2] = 2; dp[3] = 4; for(int i=4; i

[PS] 백준 11727번 2×n 타일링 2 - DP

문제 예제 풀이 이 풀이를 참고했다. 코드 import java.util.Scanner; public class Main { static Integer[] dp; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); dp = new Integer[N+1]; dp[0] = dp[1] = 1; System.out.println(caculate(N)); } static int caculate(int n) { if(dp[n] == null) { dp[n] = (caculate(n-1) +(2*caculate(n-2))) % 10007; } return dp[n]; } }

[PS] 백준 11726번 2×n 타일링 - DP

문제 예제 풀이 경우의 수를 따지면 1,2,3,5,8 ... 이렇게 결과가 나오는데, 방법은 2가지가 있다. 피보나치 수열로 푸는 방법 사각형을 그렸을 때의 경우의 수를 점화식으로 푸는 방법 2번의 경우 아래 그림에 따라 점화식 dp[n] = dp[n-1] + dp[n-2] 이 적용되는 것을 사용하는 거다. 주의할 점은 dp[n]의 값을 저장할 때 마다 10007로 나눈 값을 저장해야한다. 조건에서 n은 1000까지 커질 수 있는데, 결과가 출력할 때 나누면 특정 n을 넣었을 때 int 타입의 범위인 2^31승 약 열자리를 넘기때문이다. 코드 import java.util.Scanner; public class Main { static Integer[] dp; public static void main(..

[PS] 백준 1463번 1로 만들기 - DP

문제 예제 코드 import java.util.Scanner; public class Main { static Integer[] dp; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); dp = new Integer[N+1]; dp[0] = dp[1] = 0; System.out.println(caculate(N)); } static int caculate(int n) { if(dp[n] == null) { if(n%6==0) { dp[n] = Math.min(Math.min(caculate(n/2),caculate(n/3)),caculate(n-1)) + 1; } else i..