<stdio.han>

[문제 링크]

https://www.acmicpc.net/problem/13699

[난이도]

- Silver 4

[알고리즘]

- DP

[코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        long[] dp = new long[n + 1];

        // 초기값
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j]*dp[i-j-1];
            }
        }
        System.out.println(dp[n]);
    }
}

[풀이]

dp배열의 정의, 초기값, 점화식은 문제에서 주어진다.

남은 것은 구현하는것이다. 2중 for문을 활용하면 점화식을 구현할 수 있다.

[문제 링크]

https://www.acmicpc.net/problem/2491

[난이도]

- Silver 4

[알고리즘]

- DP

[코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] dpU = new int[N + 1];
        int[] dpL = new int[N + 1];
        dpU[0] = 1;
        dpL[0] = 1;

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int postNum = Integer.parseInt(st.nextToken());
        int max = 1;
        for (int i = 1; i < N; i++) {
            int nowNum = Integer.parseInt(st.nextToken());
            if (nowNum > postNum) {
                dpU[i] = dpU[i - 1] + 1;
                dpL[i] = 1;
            } else if (nowNum == postNum) {
                dpU[i] = dpU[i - 1] + 1;
                dpL[i] = dpL[i - 1] + 1;
            } else {
                dpL[i] = dpL[i - 1] + 1;
                dpU[i] = 1;
            }
            postNum = nowNum;
            max = Math.max(max, Math.max(dpU[i], dpL[i]));
        }
        System.out.println(max);
    }
}

[코드]

1. dp배열 정의
오름차순 dpU[n] : dp[n-1]의 값과 비교해 같거나 오름차순 형태라면 dp[n-1] + 1 아니라면 1
내림차순 dpL[n] : dp[n-1]의 값과 비교해 같거나 내림차순 형태라면 dp[n-1] + 1 아니라면 1
2. 초기값 설정
dpU[1] = 1
dpL[1] = 1
3. 점화식 작성
dpU[n] = if(nowNum>=postNum){
             dpU[n] = dpU[n-1] + 1
          } else {
              dpU[n] = 1
          }
 dpL[n] = if(nowNum<=postNum){
              dpU[n] = dpL[n-1] + 1
          } else {
              dpL[n] = 1
          }

[문제 링크]

https://www.acmicpc.net/problem/13301

[난이도]

- Silver 5

[알고리즘]

- DP

[코드]

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());


        long[] dp = new long[n + 1];
        if (n == 1) {
            System.out.println(4);
        } else {
            dp[1] = 1;
            dp[2] = 1;

            for (int i = 3; i <= n; i++) {
                dp[i] = dp[i - 2] + (dp[i - 1]);
            }

            System.out.println(dp[n]*4 + dp[n-1]*2);
        }

        br.close();
    }
}

[풀이]

피보나치 수열을 DP로 푸는 방식과 같다. 하지만 출력할 때 dp[n]*4 + dp[n-1]*2를 출력해주어야 한다.

[문제 링크]

https://www.acmicpc.net/problem/10826

[난이도]

- Silver 5

[알고리즘]

- DP

[코드]

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        int n = Integer.parseInt(br.readLine());


        if (n == 0) {
            bw.write("0");
        } else {
            BigInteger[] dp = new BigInteger[n + 1];

            dp[0] = BigInteger.ZERO;
            dp[1] = BigInteger.ONE;

            for (int i = 2; i <= n; i++) {
                dp[i] = dp[i - 2].add(dp[i - 1]);
            }

            bw.write(dp[n].toString());
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

[풀이]

bottom-up 방식

1. 문제 이해

1. n 번째 피보나치 수 찾기

2. dp 배열 정의

dp[0] = 0

dp[1] = 1

dp[2] = 1

dp[3] = 2

dp[4] = 3

dp[5] = 5

3. 초기값 설정

dp[0] = 0

dp[1] = 1

4. 점화식 작성

dp[n] = dp[n-2] + dp[n-1]

if문으로 n이 0일때 조건문으로 둔 이유 : 초기값을 설정하는 과정에서 dp[1]을 초기화하기때문에

n이 0일경우 dp[1]에 접근할 수 없어서 런타임에러(ArrayIndexOutOfBounds)가 발생한다.

[문제 링크]

https://www.acmicpc.net/problem/9625

[난이도]

- Silver 5

[알고리즘]

- DP

[코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int K = Integer.parseInt(br.readLine());

        // dp 배열 정의
        int[] dpA = new int[K + 1]; // K + 1인 이유 0번 눌렀을 때 부터 K번 눌렀을 때 까지의 상태를 저장하기 위함
        int[] dpB = new int[K + 1];

        // 초기값 설정
        dpA[0] = 1;
        dpB[0] = 0;

        // dp 배열 채우기
        for (int i = 1; i <= K; i++) {
            dpA[i] = dpB[i-1];
            dpB[i] = dpA[i - 1] + dpB[i - 1];
        }

        System.out.println(dpA[K] + " " + dpB[K]);
    }
}

[풀이]

1. 문제 이해 및 분석
버튼을 누를때 마다 a는 b로 b는 ba로 바뀜. 0번 눌렀을 때 부터 K번 누를때 까지 를 체크해야하므로 bottom-up방식을 사용

2.DP 배열 정의
dpA[i] 는 버튼을 i번 눌렀을 때 화면에 있는 a의 개수
dpB[i] 는 버튼을 i번 눌렀을 때 화면에 있는 b의 개수

3.초기값 설정
dpA[0] = 1
dpB[0] = 0

4. 점화식 작성
dpA[i] = dpB[i-1] : 이전 단계의 b가 현재단계의 a로 바뀜
dpB[i] = dpA[i-1] + dpB[i-1] + dpB[i-1] : 이전단계의 a가 b로 바뀌고, 이전 단계의 b는 ba로 바뀜

5.DP 배열 채우기
1부터 K까지의 모든 단계를 차례로 계산해 dp배열을 채움

6.최종 결과 출력
버튼을 k번 눌렀을 때 a와 b의 개수 출력