백준 1912번 연속합

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        int d[] = new int[n];

        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            d[i] = a[i];
        }

        int answer = d[0];
        for(int i = 0; i < n; i++) {
            if(i == 0) {
                continue;
            }
            d[i] = Math.max(d[i - 1] + a[i], a[i]);
            answer = Math.max(answer, d[i]);
        }
        System.out.println(answer);
    }
}

D[i] = i번째 수로 끝나는 가장 큰 연속합
경우의 수는 두가지다.

1. i번째 수가 i-1번째와 연속일 때
   D[i] = D[i-1] + A[i]
2. i번째 수가 새로운 연속을 시작할 때
   D[i] = A[i]

따라서, D[i] = max(D[i-1] + A[i], A[i])가 된다.

결과

백준 1699번 제곱수의 합

문제

나의 풀이

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[n + 1];
        for(int i = 1; i <= n; i++) {
            d[i] = i;
            for(int j = 1; j * j <= i; j++) {
                d[i] = Math.min(d[i], d[i - j * j] + 1);
            }
        }
        System.out.println(d[n]);
    }
}

D[i] = i를 제곱수의 합으로 나타냈을 때 필요한 항의 최소 개수이다.
마지막 항이 i라고 했을 때 앞의 제곱 수의 합은 D[n-i2]이 되고 따라서
D[n] = min(D[n - i2]) + 1이 된다.
i제곱의 범위는 1이상 n 이하이다.
초기값을 0으로 하면 안되기 때문에 i로 해준다.

결과

백준 2225번 합분해

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long d[][] = new long[k + 1][n + 1];
        d[0][0] = 1;
        for(int i = 1; i <= k; i++) {
            for(int j = 0; j <= n; j++) {
                for(int l = 0; l <= j; l++) {
                    d[i][j] += d[i - 1][j - l];
                    d[i][j] %= 1000000000L;
                }
            }
        }
        System.out.println(d[k][n]);
    }
}

D[K][N] = 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수
마지막에 더하는 수를 L이라고 하면
그 앞전까지의 경우를 나타내는 값은 D[K-1][N-L]이 된다.
따라서 D[K][N] = 시그마 D[K-1][N-L]이 된다.
L의 범위는 0이상 N이하이다.

결과