<stdio.han>

[문제 링크]

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

[난이도]

- Silver 3

[알고리즘]

- DP

[코드]

import java.io.*;

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][2];

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

        // DP 배열 채우기
        for (int i = 2; i <= N; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-1][1];
            dp[i][1] = dp[i-1][0];
        }

        // 최종 결과 출력
        long result = dp[N][0] + dp[N][1];
        System.out.println(result);
    }
}

[풀이]

1. 문제 이해

0 으로 시작하지 않는다.

1이 두번 연속으로 나타나지 않는다.

2. dp 배열 정의

 n=1 일때  {1} = 1
 n=2 일때 {10} = 1
 n=3 일때 {100, 101} = 2
 n=4 일때 {1000, 1001, 1010} = 3
 n=5 일때 {10000, 10001, 10010, 10100, 10101} = 5
 n=6 일때 {100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010} = 8

dp[n] = dp[n-1]의 길이만큼 for문을 돌며 dp[n-1]의 각 원소뒤에 0과 1을 추가한다. 마지막 자리가 1일경우 0만 추가.
새로만든 원소들을 dp[n]에 넣는다.

이 로직을 점화식으로 만들고 구현할 아이디어가 모자라서 챗gpt의 도움을 빌렸다.

dp[i][0] : i자리 이친수 중 마지막 자리가 0인 이친수의 개수

dp[i][1] : i자리 이친수 중 마지막 자리가 1인 이친수의 개수

3. 초기값 설정

dp[1][0] = 0

dp[1][1] = 1

4. 점화식 작성

dp[i][0] = dp[i-1][0] + dp[i-1][1] : 마지막 자리가 0인 경우는 i-1자리 이친수에서 마지막 자리가 0인 경우와 1인 경우 모두에서 올 수 있다.

dp[i][1] = dp[i-1][0] : 마지막 자리가 1인 경우는 i-1자리 이친수에서 마지막 자리가 0인 경우에서만 올 수 있다.

5. 출력

N자리의 이친수의 개수 = dp[N][0] + dp[N][1]

[문제 링크]

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의 개수 출력

[문제 링크]

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

[난이도]

- Silver 5

[알고리즘]

- DP

[코드]

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

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

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[100001];

        dp[0] = INF;
        dp[1] = INF;
        dp[2] = 1;
        dp[3] = INF;
        dp[4] = 2;
        dp[5] = 1;

        for (int i = 6; i <= n; i++) {
            dp[i] = Math.min(dp[i - 2], dp[i - 5]) + 1;
        }
        System.out.println(dp[n] == INF ? -1 : dp[n]);
    }
}

[풀이]

DP로 문제를 풀어보았다. Bottom-up방식으로 풀었다.

1. 문제를 하위문제로 쪼갠다

dp[1] = 동전을 못거슬러줌
dp[2] = 2원짜리 하나 거슬러줌
dp[3] = 2원짜리 하나 거슬러줘도, 남은1원을 못거슬러줌
dp[4] = 2원짜리로 2개
dp[5] = 5원짜리 하나 
dp[6] = 5원짜리 하나, 남은 1원못거슬러줌 
            2원짜리 3개거슬러줌

2. 관계를 수식화
5원을 거슬러줄때랑 2원을 거슬러줄때랑을 둘 다 고려해야함

dp[n] = Math.min(dp[n-2], dp[n-5]) + 1

3. 초기값 설정

dp[0] = INF

dp[1] = INF

dp[2] = 1

dp[3] = INF

dp[4] = 2

dp[5] = 1

[출처]

https://tang25.tistory.com/entry/%EC%9E%90%EB%B0%94%EB%B0%B1%EC%A4%80-9625%EB%B2%88-%EA%B1%B0%EC%8A%A4%EB%A6%84%EB%8F%88%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%EC%97%84%ED%83%B1

[문제 링크]

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

[난이도]

- 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 n = Integer.parseInt(br.readLine());
        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 1;
        for (int i = 4; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 3]) + 1;
        }
        if (dp[n] % 2 == 0) {
            System.out.println("CY");
        } else {
            System.out.println("SK");
        }
    }
}

[풀이]

DP를 푸는 순서

1. 상태 결정

• dp[1] : 돌이 1개 있으면 상근이가 먼저 1개를 가져가므로 상근이 승리
• dp[2] : 상근이가 1개를 가져가고 남은 1개를 창영이가 가져가므로 창영 승리.
• dp[3] : 상근이가 처음부터 3개를 가져가면 상근 승리
• dp[4] : 상근이가 처음에 1개를 가져가면 창영이가 3개를 가져가서 창영 승리. 상근이가 처음에 3개를 가져가면 창영이가 1개를 가져가서 창영 승리.
• dp[5] : 상근이가 처음에 1개를 가져가면 창영이가 1개를 가져가든 3개를 가져가든 3개나 1개가 남아 상근이가 나머지를 가져가면 상근 승리. 상근이가 처음에 3개를 가져가면 창영이는 1개밖에 못가져가므로 나머지 1개를 상근이가 가져가 상근 승리.
•  

2. 관계를 수식화

• 돌을 1개를 가져가는 경우와 3개를 가져가는 경우 둘 다 고려해 최소값을 구한다.
• dp[n] = Math.min(dp[n-1], dp[n-3]) + 1
• dp[n] 이 홀수면 상근 승리, 짝수면 창영 승리

3. 초기값 정하기

• dp[1] = 1
• dp[2] = 2
• dp[3] = 1

[출처]

https://propercoding.tistory.com/21