Algorithm Study #3 (Dynamic Programming (DP) - 1.3)

jakeseo_me·2019년 2월 18일
0

java algorithm study

목록 보기
10/18

이친수

  • boj.kr/2193
  • 이진수에서 특별한 속성이 추가됨
    1. 0으로 시작하지 않는다.
    2. 1이 두번 연속으로 나타나지 않는다.
    • 이를테면 1, 10, 100, 101, 1000, 1001이 이친수
      • 0010101이나 101101은 각각 1,2 번 규칙에 위배되므로 이친수가 아니다.
  • 케이스 분할
    • n번째 자리에 0이 온 경우
      • n번째 자리에 1이 온 경우
      • 확실한 것들은 fix시키고 유동적인 것들만 보는 능력이 필요
        • ex) n=4일때
          1. 앞의 10은 무조건 고정
          2. 맨 뒤의 숫자는 0 또는 1만 가능하다.
          1. 가운데 올 수 있는 숫자는?
            3. 1. 맨 뒤가 0일 때 0과 1 둘 다 가능
            3. 2. 맨 뒤가 1일 때는 0만 가능
          • 케이스 분할을 이용하여 올 수 있는 숫자를 제한하고 쉽게 풀 수 있다.
  • 구현
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.math.BigInteger;

    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());

            BigInteger[] d = new BigInteger[91];

            d[1] = new BigInteger("1");
            d[2] = new BigInteger("1");
            d[3] = new BigInteger("2");
            d[4] = new BigInteger("3");
            d[5] = new BigInteger("5");

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

            System.out.println(d[n]);
        }
    }

쉬운 계단 수

  • 이친 수와 비슷
  • 인접한 모든 자리수의 차이가 1이 남
    • ex) 456456
  • 길이가 N인 계단 수의 개수는?
  • 접근법
    • 이친수와 마찬가지로 끝에 L이 온다고 가정하고 풀면 쉽다.
      • D[N][L]처럼 2차원 배열을 만든다. N은 자리수의 개수고 L은 끝에 오는 숫자이다.
      • D[3][2]는 3자리수일 때, 끝이 2로 끝나는 계단 수의 갯수이다.
  • 구현
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;

    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[][] d = new long[101][101];
            int mod = 1000000000;

            for (int i = 1; i <= 9; i++)
                d[1][i] = 1;

            for(int i=2; i<=n; i++) {
                for (int j=0; j<=9; j++) {
                    if(j-1 < 0) d[i][j] = d[i-1][j+1];
                    else d[i][j] = d[i-1][j-1] + d[i-1][j+1];
                    d[i][j] %= mod;
                }
            }

            long sum = 0;
            for (int i = 0; i <= 9; i++)
                sum += d[n][i];

            System.out.println(sum % mod);
        }
    }

오르막 수

  • boj.kr/11057
  • 수의 자리가 오름차순을 이루는 수
  • 인접한 수가 같아도 오름차순으로 친다.
  • 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 문제
  • 수는 0으로 시작할 수 있다.
    • ex) 123345, 357, 88888888, 15559999
  • 문제 해결 포인트
    • N=2부터 숫자가 1증가할 때마다 올 수 있는 숫자의 범위를 잘 계산하면 된다.
      • 간단하게 생각했을 때, N=2일 때, D[N][1] = D[N][0] + D[N][1] 인 것을 알면 된다.
        • 1로 끝나는 2자리 수는 01 11 여기서 1 앞에 붙는 0 1은 이전 배열에서 참조하면 된다.
  • 구현
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.math.BigInteger;

    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());
            BigInteger[][] d = new BigInteger[1001][1001];


            for(int i=1; i<=2; i++){
                for(int j=0; j<=9; j++){
                    if( i == 1) d[i][j] = new BigInteger("1");
                    if( i == 2) d[i][j] = new BigInteger(Integer.toString(j+1));
                }
            }

            for(int i=3; i<=n; i++){
                for(int j=0; j<=9; j++){
                    d[i][j] = new BigInteger("0");
                    for(int k=0; k<=j; k++){
                        d[i][j] = d[i][j].add(d[i-1][k]);
                    }
                }
            }

            BigInteger sum = new BigInteger("0");
            for(int i=0; i<=9; i++)
                sum = sum.add(d[n][i]);

            System.out.println(sum.mod(new BigInteger("10007")));
        }
    }

스티커

  • boj.kr/9465
  • 조건
    • 스티커 2n개가 2Xn모양으로 배치되어 있다.
    • 스티커 한 장을 떼면 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없다.
    • 점수의 최대 합을 구하는 문제
  • 전략
    • 가장 큰 숫자를 떼는 것이 옳은가?
      - 아니다. 주변의 숫자들이 아주 근소한 차로 큰 숫자들로 이루어져있다면 오히려 손해.
      • 스티커를 떼는 임의의 순서를 정하자
      • 왼쪽에서 오른쪽으로 위 아래 스티커를 뗄지 말지 결정한다고 가정하자.
      • 케이스별로 나눠서 풀자.
        • 0번 위 아래 모두 안 떼는 것 (XX)
          • 1번 위 떼고 아래는 안 떼는 것 (OX)
          • 2번 위 안 떼고 아래는 떼는 것 (XO)
    • 매 루프마다 어떤 연산을 수행해야 할까?
      - 위에 정의한 0, 1, 2번 케이스에 대한 최대 값을 3개의 배열에 각각 넣어야 한다.
      	- 0번 케이스의 경우
          	- 이전 케이스로 0, 1, 2번 모두 올 수 있음
              - max(d[i-1][0], d[i-1][1], d[i-1][2])
          - 1번 케이스의 경우
          	- 이전 케이스로 0, 2번 올 수 있음
              - 그리고 자신의 스티커 점수도 합산해줘야 함
              - max(d[i-1][0], d[i-1][2]) + 스티커[i][1]
          - 2번 케이스의 경우
          	- 1번과 비슷
              - max(d[i-1][0], d[i-1][1]) + 스티커[i][2]
  • 구현
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;

    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());
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<t; i++) {

                int n = Integer.parseInt(br.readLine());
                int[][] stickers = new int[n][3];
                int[][] d = new int[n][3];
                StringTokenizer st0 = new StringTokenizer(br.readLine(), " ");
                StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");

                for(int j=0; j<n; j++){
                    stickers[j][1] = Integer.parseInt(st0.nextToken());
                    stickers[j][2] = Integer.parseInt(st1.nextToken());
                }

                d[0][0] = 0;
                d[0][1] = stickers[0][1];
                d[0][2] = stickers[0][2];

                for(int j=1; j<n; j++){
                    d[j][0] = Math.max(Math.max(d[j-1][0], d[j-1][1]), d[j-1][2]);
                    d[j][1] = Math.max(d[j-1][0], d[j-1][2]) + stickers[j][1];
                    d[j][2] = Math.max(d[j-1][0], d[j-1][1]) + stickers[j][2];
                }

                sb.append(Math.max(Math.max(d[n-1][0], d[n-1][1]), d[n-1][2]) + "\n");
            }

            System.out.print(sb.toString());
        }
    }

포도주 시식

  • boj.kr/2156
  • 조건
    • 1부터 n까지의 포도주가 테이블 위에 순서대로 놓여있고 각 포도주의 양은 다를 수 있다.
    • 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치로 놓아야 한다.
      • 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
      • 최대한 많은 양의 포도주를 맛봤을 때 그 합은?
    • ex) 6개의 포도주 잔이 있고 각각의 잔에 6, 10, 13, 9, 8, 1만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
  • 전략
    • 케이스별 분리
      - 안 마신 상태일 때
      	- 이전 상태로 아무거나 올 수 있음
          - max(이전에 안마심, 이전에 1잔, 이전에 2잔)
      - 1잔 마신 상태일 때
      	- 이전에 안마심 + 이번 잔의 양 
      - 2잔 마신 상태일 때
      	- 이 전에 1잔 마심 + 이번 잔의 양
  • 구현
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;

    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[] podojus = new int[n];
            int[][] d = new int[n][3];

            for(int i=0; i<n; i++){
                podojus[i] = Integer.parseInt(br.readLine());
            }

            d[0][0] = 0;
            d[0][1] = podojus[0];
            d[0][2] = podojus[0];

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

            System.out.println(Math.max(Math.max(d[n-1][0], d[n-1][1]), d[n-1][2]));
        }
    }
profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. Javascript를 좋아합니다.

0개의 댓글