백준 1463번 1로 만들기

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int d[] = new int[n + 1];
        d[1] = 0;
        for(int i = 2; i <= n; i++) {
            d[i] = d[i - 1] + 1;
            if(i % 2 == 0) {
                d[i] = Math.min(d[i], d[i / 2] + 1);
            }
            if(i % 3 == 0) {
                d[i] = Math.min(d[i], d[i / 3] + 1);
            }
        }
        System.out.println(d[n]);
    }
}

D[N] = N을 1로 만드는 최소 연산 횟수

1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 라는 1번 연산을 수행하는 연산 횟수는 N에서 N/3을 할 때 까지 1번과 N/3에서 1이 될때까지는 D[N/3]이므로 1 + D[N/3]이 된다.
2. X가 2로 나누어 떨어지면, 2로 나눈다. 라는 2번 연산을 수행하는 연산 횟수는 N에서 N/2를 할 때 까지 1번과 N/2에서 1이 될때까지 최소 연산 횟수는 D[N/2]이므로 1 + D[N/2]이 된다.
3. 1을 뺀다. 라는 1번 연산을 수행하는 연산 횟수는 1 + D[N - 1]이 된다.

그렇기 때문에 D[N] = min(D[N / 3], D[N / 2], D[N - 1]) + 1이 된다.

초기화할 수는 D[1] = 0이다.

결과

백준 11726번 2xn 타일링

문제

나의 풀이

import java.util. *;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long d[] = new long[1001];
        d[1] = 1;
        d[2] = 2;
        
        for(int i = 3; i <= n; i++) {
            d[i] = (d[i - 1] + d[i - 2]) % 10007;
        }
        
        System.out.println(d[n]);
    }
}

D[n] = 2xn 직사각형을 채우는 방법의 수라 하자.
2xn 직사각형이 이을 때 가장 오른쪽에 타일을 놓을 수 있는 방법은 총 2가지다. (세로1개, 가로2개)

1. 세로 사각형을 놓는 경우일 때
   -> 세로 사각형 제외하고 크기가 2x(n-1)이 되고 경우의 수는 D[n-1]이 된다.
2. 가로 사각형 2개를 놓는 경우일 때
   -> 가로 사각형 2개 제외하면 크기가 2x(n-2)이 되고 경우의 수는 D[n-2]가 된다.

그렇기 때문에 D[n] = D[n - 1] + D[n - 2]가 된다.
초기화할 수 는 D[1] = 1, D[2] = 2이다.

결과

백준 11727번 2xn 타일링 2

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d[] = new int[1001];
        d[0] = 1;
        d[1] = 1;
        
        for(int i = 2; i <= n; i++) {
            d[i] = d[i - 1] + d[i - 2] * 2;
            d[i] %= 10007;
        }
        System.out.println(d[n]);
    }
}

D[n] = D[n - 1] + 2 * D[n - 2]

결과

백준 9095번 1, 2, 3 더하기

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int[] d = new int[11];
        d[0] = 1;
        
        for(int i = 1; i <= 10; i++) {
            for(int j = 1; j <= 3; j++) {
                if(i - j >= 0) {
                    d[i] += d[i - j];
                }
            }
        }
        
        int t = sc.nextInt();
        for(int i = 0; i < t; i++) {
            int n = sc.nextInt();
            System.out.println(d[n]);
        }
    }
}

D[n] = n을 1, 2, 3의 합으로 나타내는 방법의 수라 하자.
가장 끝으로 더하는 수의 종류는 1, 2, 3이 있다.

1. 1인 경우 => D[n - 1] + 1
2. 2인 경우 => D[n - 2] + 2
3. 3인 경우 => D[n - 3] + 3

D[n] = D[n - 1] + D[n - 2] + D[n - 3]이 된다.

초기화한 수는 D[0] = 1이다.

결과