이친수

  • 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. 가운데 올 수 있는 숫자는?
              1. 맨 뒤가 0일 때 0과 1 둘 다 가능
              1. 맨 뒤가 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로 끝나는 계단 수의 갯수이다.
  • 구현
    ```java
    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은 이전 배열에서 참조하면 된다.
- 구현
```java
    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]
  • 구현
    ```java
    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잔 마심 + 이번 잔의 양
- 구현
```java
    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]));
        }
    }