PS(Java)/백준

[PS] 백준 2193번 이친수 - DP

문제 예제 풀이 이 문제도 앞서 쭉 푼 문제들과 비슷하다. 오히려 조건이 더 단순해서 쉽게 풀었다. 이친수의 조건은 다음과 같다. 0과 1만 사용 (이진수) 1이 연속되면 안된다. 0으로 시작하지 않는다. dp[자리길이][마지막자릿값] 배열을 선언한다. 마지막 자릿값이 0이면 뒤에 0이나 1이 올 수 있다.(두 가지 경우의 수) 마지막 자릿값이 1이면 뒤에 0만 올 수 있다.(한 가지 경우의 수) ​ 4자리와 5자리 이친수의 예를 들어보자 dp[4][0] = {1000, 1010} dp[4][1] = {1001} dp[5][0] = {10000, 10100, 10011} dp[5][1] = {10001, 10101} 따라서 dp[n][0] = dp[n-1][0] + dp[n-1][1] 이고 dp[n][1..

[PS] 백준 11057번 오르막 수 - DP

문제 예제 풀이 이 문제는 쉬운 계단 수 문제의 연장선이다. 주의할 점은 계단 수와 달리 숫자를 0부터 시작할 수 있다. 똑같이 dp[자릿수길이][마지막자릿수] 이차원배열을 사용하였고, 다음 필기와 같은 규칙성을 찾을 수 있다. 따라서 도출되는 점화식 dp[n][i] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2] + ... + dp[n-1][i]를 사용하여 푼다. 코드 import java.util.Arrays; import java.util.Scanner; public class Main { final static long mod = 10007; public static void main(String[] args) { Scanner sc = new Scanner(System.in..

[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..