백준 11057번 오르막수

문제

나의 풀이

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[n + 1][10];
        for(int i = 0; i <= 9; i++) {
            d[1][i] = 1;
        }
        
        for(int i = 2; i <= n; i++) {
            for(int j = 0; j <= 9; j++) {
                for(int k = 0; k <= j; k++) {
                    d[i][j] += d[i - 1][k];
                    d[i][j] %= 10007;
                }
            }
        }
        
        long answer = 0;
        for(int i = 0; i < 10; i++) {
            answer += d[n][i];
        }
        System.out.println(answer % 10007);
    }
}

D[i][j] = 길이가 i이고 마지막 숫자가 j인 오르막 수의 개수
D[1][i] = 1
D[i][j] += D[i-1][k] (0 <= k <= j)

결과

백준 9465번 스티커

문제

나의 풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while(t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            long a[][] = new long[n + 1][2];
            String[] str = br.readLine().split(" ");
            for(int i = 1; i <= n; i++) {
                a[i][0] = Long.parseLong(str[i - 1]);
            }

            str = br.readLine().split(" ");
            for(int i = 1; i <= n; i++) {
                a[i][1] = Long.parseLong(str[i - 1]);
            }

            long d[][] = new long[n + 1][3];
            for(int i = 1; i <= n; i++) {
                d[i][0] = Math.max(d[i - 1][0], Math.max(d[i - 1][1], d[i - 1][2]));
                d[i][1] = Math.max(d[i - 1][0], d[i - 1][2]) + a[i][0];
                d[i][2] = Math.max(d[i - 1][0], d[i - 1][1]) + a[i][1];
            }

            long answer = Math.max(d[n][0], Math.max(d[n][1], d[n][2]));
            System.out.println(answer);
        }
    }
}

D[i][j] = 2xi 에서 얻을 수 있는 최대 점수, i번 열에서 뜯는 스티커는 j
j = 0 -> 뜯지 않음 => i-1열에서 0, 1, 2 가능
j = 1 -> 위쪽 스티커를 뜯음 => i-1열에서 0,2 가능
j = 2 -> 아래쪽 스티커를 뜯음 => i-1열에서 0,1 가능

• 뜯지 않음(D[i][0])
  • i-1 열에서 스티커를 어떻게 뜯었는지 상관 없음
  • max(D[i-1][0], D[i-1][1], D[i-1][2])
• 위쪽 스티커를 뜯음(D[i][1])
  • i-1열에서 위쪽 스티커는 뜯으면 안된다.
  • max(D[i-1][0], D[i-1][2])) + A[i][0]
• 아래쪽 스티커를 뜯음(D[i][2])
  • i-1열에서 아래쪽 스티커는 뜯으면 안된다.
  • max(D[i-1][0], D[i-1][1])) + A[i][1]

결과

백준 2156번 포도주 시식

문제

나의 풀이

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 + 1];
        for(int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        
        int d[] = new int[n + 1];
        d[1] = a[1];
        if(n >= 2) {
            d[2] = a[1] + a[2];
        }
        for(int i = 3; i <= n; i++) {
            d[i] = d[i - 1];
            d[i] = Math.max(d[i], d[i - 2] + a[i]);
            d[i] = Math.max(d[i], d[i - 3] + a[i - 1] + a[i]);
        }
        
        int answer = d[1];
        for(int i = 2; i <= n; i++) {
            answer = Math.max(answer, d[i]);
        }
        System.out.println(answer);
    }
}

D[i] = A[1], ..., A[i] 까지 포도주를 마셨을 때 마실 수 있는 포도주의 최대양

i에게 가능한 경우

• i번째 포도주를 마시는 경우 : D[i-1] + A[i]
• i번째 포도주를 마시지 않는 경우 : D[i-1]

=> D[i] = max(D[i - 1] + A[i], D[i - 1])

but, 위의 식은 포도주를 연속해서 3잔 마시면 안되는 경우를 처리하지 못함

---

D[i][j] = A[1], ..., A[i] 까지 포도주를 마셨을 때, 마실 수 있는 포도주의 최대 양. A[i]는 j번 연속해서 마신 포도주이다.

• D[i][0] = 0번 연속해서 마신 포도주 -> A[i]를 마시지 x => max(D[i - 1][0], D[i-1][1], D[i-1][2])
• D[i][1] = 1번 연속해서 마신 포도주 -> A[i-1]을 마시지 x => D[i-1][0]+A[i]
• D[i][2] = 2번 연속해서 마신 포도주 -> A[i-1]을 마시고, A[i-2]는 마시지 x => D[i-1][1] + A[i]

결과