[JAVA] 백준 dp - 실버모음(10844 쉬운 계단 수, 11052 카드 구매하기, 11057 오르막 수)

 

배낭문제와 비슷한 류의 문제를 풀어봤는데, dp문제가 많이 약하다는 걸 알아냈다!

배열을 종이에 그리지 않으면 헷길리고, 문제를 제대로 풀 수 없는게 슬펐다. 그래서 손으로 그리지 않아도 머릿속으로 떠오르도록 많이 풀어 익숙해지려고 한다. 

 

 

 

10844 쉬운 계단 수 - 실버1

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

10844번: 쉬운 계단 수

 

• dfs로도 풀릴 것 같다 -> 시간초과남 ㅜ
• dp로 풀어야겠다고 생각했지만 아이디어가 떠오르지 않아 구글링을 해봤다

 

풀이 설명

• (dp가 진짜 참신한 것 같다. 이렇게 푸는 게 너무 신기하고 재밌다)
• 행은 1자리수 ~ N자리수
• 열은 어떤 자리로 시작하는 지 나타냄

 

초기값

• 한자리 수이고, 1로 시작하는 수는 1개이다
• 0인 경우는 이후 계산을 위해 일단 1로 표시

 

이후 값

• 3자리인데 3으로 시작하는 애는 (2자리, 2로 시작하는 애) + (2자리, 4로 시작하는 애) 이다.
• 예외로 3자리인데 9로 시작하는 애는 9에서 8로 갈 수밖에 없기 때문에 (2자리, 8로 시작하는 애)와 수가 같다
• 0으로 시작할 수는 없지만, 이후 10123~ 이렇게 될 수 있기 때문에 0으로 시작하는 애도 계산은 해준다 = (2자리, 1로 시작하는 애)
  • 0으로 시작하는 경우는 나중에 result값에 더할 때 포함하지 않도록 만들 생각이다

 

• 계산되는 느낌은 이런 느낌이다

 

풀이

public class Main {
  static long result = 0;
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());

    long[][] arr = new long[N+1][10];
    for (int i =0; i<10; i++)
      arr[1][i] = 1L;

    for (int i =2; i<=N; i++) {
      for (int j=0; j<10; j++) {
        if (j == 0 || j == 9) {
          if (j == 0)
            arr[i][j] = arr[i-1][j+1];
          else
            arr[i][j] = arr[i-1][j-1];
        } else {
          arr[i][j] = (arr[i-1][j-1] % 1000000000 + arr[i-1] [j+1] % 1000000000) % 1000000000;
        }
      }
    }

    for (int i =1; i<10; i++) 
      result += arr[N][i] % 1000000000;

    System.out.println(result % 1000000000);
  }
}

• 위에서 설명한 2차원 배열을 모두 채우고
• N번째 행의 1열부터 9열까지 더하여 출력하면 된다
• 주의점
  • 더한 값이 long이 될 수 있다는 걸 꼭 생각하기
  • 모듈러 연산을 잘 써야 오버플로우가 발생하지 않음!! 주의
  • 1000000000 이 숫자를 변수로 설정하면 더 보기 좋을듯 MOD이런걸로

 

 

11052 카드 구매하기 - 실버1

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

11052번: 카드 구매하기

 

• 전형적인 dp문제 느낌이 난다
• 카드 개수를 열로, 카드묶음을 행으로 하여 2차원 배열을 그린다
• 각 행에서는 해당하는 카드묶음을 넣었을 때와 넣지 않았을 때의 최댓값을 비교하여 갱신해준다
• 2차원 배열은 다음과 같음

        0 1 2 3 4 5 6
x      0 0 0 0 0 0 0 
P1    0
P2    0
P3    0

 

• arr[i][j] = max( arr[i-1][j], arr[i-1][ j- cardCnt ] + value ) 이런식으로 갱신해주면 될듯
• 카드묶음은 중복선택이 가능하기 때문에 cardCnt에 카드묶음 선택 횟수인 cnt를 곱해야할 것 같다
• 최종 점화식은 arr[i][j] = max( arr[i-1][j], arr[i-1][ j- cardCnt*1] + value*1, arr[i-1][ j- cardCnt*2] + value*2, ...)
  • cnt는 1부터 시작하여 N을 넘지 않는 횟수까지임 

 

풀이

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int[] price = new int[N+1]; //0열은 사용하지 않는다, 최대 10,000,000

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i =1; i<price.length; i++)
      price[i] = Integer.parseInt(st.nextToken()); //i개 묶음에 대한 가격

    int[][] arr = new int[N+1][N+1];

    for (int i =1; i<arr.length; i++) {
      for (int j=1; j<arr.length; j++) {
        int max = arr[i-1][j];
        int cnt = 1;
        while (i*cnt <= j) {
          if (max < arr[i-1][j-i*cnt] + price[i]*cnt)
            max = arr[i-1][j-i*cnt] + price[i]*cnt;
          cnt ++;
        }

        arr[i][j] = max;
      }
    }

    System.out.println(arr[N][N]);
  }
}

• while문으로 개수가 1개일 때, 개수가 2개일 때 모두 체크해줬다
• 최대의 가격이 될 때 arr[i][j]를 갱신한다

 

 

 

11057 오르막 수 - 실버1

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

11057번: 오르막 수

 

• 위에 계단 수랑 비슷한 맥락의 문제다
• 2차원 배열로 행은 자릿수(1~N)로 열은 시작하는 수(0~N)로 해두면 될 것 같다
• 0~9 로 시작하는 오르막 수를 체크한다
  • 8로 시작하는 길이가 2일 때 오르막 수 개수는 ( 0으로 시작하는 길이1 오르막 수 개수 + ... + 8로 시작하는 길이1 오르막 수 개수 )와 같다
  • 0으로 시작하는 길이가 2일 때 오르막 수 개수는 ( 0으로 시작하는 길이가 1일 때 오르막 수 개수 )와 같다. 이 경우만 예외로 잘 처리해주면 됨
• 배열 다음과 같은 꼴이다

     0 1 2 3 4 5 6 7 8 9

1   1 1 1 1 1 1 1 1 1 1

2   1

3   1

4   1

• 10007로 나누라고 하니까 모듈러연산을 잘 써줘야할 것 같다

 

 

풀이

public class Main {
  static final int MOD = 10007;
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int[][] arr = new int[N+1][10];

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

    for (int i =2; i<arr.length; i++) {
      arr[i][0] = 1;
      for (int j=1; j<=9; j++) {
        for (int k=0; k<=j; k++)
          arr[i][j] += arr[i-1][k] % MOD;
      }
    }

    int result = 0;
    for (int i =0; i<10; i++)
      result += arr[N][i] % MOD;

    System.out.println(result%MOD);
  }
}

• for문 안에 다시 for문을 넣어 0부터 더해주도록 구현했다

 

 

 

 

 

 

 

 

이제 슬슬 dp문제가 익숙해지고 있다! 처음엔 너무 어려웠는데 익숙해지면 어렵지 않다. 

다음엔 골드문제 몇 개를 풀어보려고 한다