[JAVA] 백준 dp - 골드모음(2096 내려가기, 2225 합분해, 2293 동전 1, 2294 동전 2)

 

2096 내려가기 - 골드5

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

2096번: 내려가기

 

• 작은 문제가 바로 보이는 문제!
• 그냥 배열을 내려가면서 가능한 최대값, 최솟값을 구하면 될 것 같다
• 마지막 줄에 도착했을 때 최댓값 3개중 가장 최대인 값/ 최솟값 3개 중 가장 최소인 값이 답

 

class Value {
  int min;
  int max;

  public Value(int min, int max) {
    this.min = min;
    this.max = max;
  }
}

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

    Value[][] arr = new Value[num][3];

    StringTokenizer st;
    for (int i =0; i<num; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int c = Integer.parseInt(st.nextToken());

      arr[i][0] = new Value(a,a);
      arr[i][1] = new Value(b,b);
      arr[i][2] = new Value(c,c);
    }

    for (int i =1; i<num; i++) {
      //최댓값
      arr[i][0].max += Math.max(arr[i-1][0].max, arr[i-1][1].max);
      arr[i][1].max += max(arr[i-1][0].max, arr[i-1][1].max, arr[i-1][2].max);
      arr[i][2].max += Math.max(arr[i-1][1].max, arr[i-1][2].max);

      //최솟값
      arr[i][0].min += Math.min(arr[i-1][0].min, arr[i-1][1].min);
      arr[i][1].min += min(arr[i-1][0].min, arr[i-1][1].min, arr[i-1][2].min);
      arr[i][2].min += Math.min(arr[i-1][1].min, arr[i-1][2].min);
    }

    int max = max(arr[num-1][0].max, arr[num-1][1].max, arr[num-1][2].max);
    int min = min(arr[num-1][0].min, arr[num-1][1].min, arr[num-1][2].min);

    System.out.println(max + " " + min);
  }

  static int max(int a, int b, int c) {
    return Math.max(Math.max(a,b), c);
  }

  static int min(int a, int b, int c) {
    return Math.min(Math.min(a,b), c);
  }
}

• 처음엔 3차원 배열로 풀었다가 가독성 문제로 객체배열로 바꿨다
  • 배열의 위치를 저장 + max값과 min값을 저장하기 위함
• 3차원 배열로 푼다고 해도 인덱스가 조금 헷갈린다는 걸 제외하면 전혀 어렵지 않은 문제다

 

 

 

2225 합분해 - 골드5

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

2225번: 합분해

 

• 감도 안잡혀서 구글링함
• 행은 정수 k개/ 열은 더해서 N이 되는 수 로 잡고 배열을 채워나가면 된다

 

일단 초기화를 해준다. 1개로 x를 만드는 경우는 한 가지 밖에 없고, x개로 0을 만드는 경우는 0000 밖에 없기 때문에 1

 

• 2개 숫자로 1을 만드는 경우는 (1개로 0만들기) + (1개로 1만들기) 경우의 수와 같다
• 2개 숫자로 1이하의 수를 만든 후 하나만 더하면 3개숫자로 1을 만들 수 있기 때문이다
  • 0~N까지 더할 수 있으니 가능함

 

• 나머지도 마찬가지다

 

+) 2개 숫자로 2만드는 경우는 (2개 숫자로 1만드는 경우) + (1개 숫자로 2만드는 경우) 와 같다

2개 숫자로 1만드는 경우는 [1][0] + [1][1] 이기 때문 -> 이미 더해져있으니 굳이 순환해서 더할 필요는 없음 ㅇㅇ

 

 

풀이

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    Integer MOD = 1000000000;

    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

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

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

    for (int i =2; i<K+1; i++) {
      for (int j=1; j<N+1; j++)
        arr[i][j] = (arr[i][j-1]%MOD + arr[i-1][j]%MOD)%MOD;
    }

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

• 배열을 만들어주고, 1행 전체와 0열 전체를 1로 초기화한다
• 2행 1열부터 위와 왼쪽을 더하며 채워나가면 됨
• 마지막 arr[K][N] 을 출력한다

 

 

2293 동전 1 - 골드5

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

2293번: 동전 1

 

• 유명한 동전 거스름돈 문제다!
• 각 동전이 다른 동전들의 배수로 표현될 수 있으면 그리디하게 풀 수 있지만, 예제에서 125를 쓰는 걸 보면 dp로 풀어야한다
• 가치가 1원일 때, 2원일 때, ... , k원일 때를 구해가면 될 것 같다
• 각 동전을 사용할 때, 1개 사용할 때, 2개 사용할 때를 모두 더한 값이 경우의 수다
• 다음과 같이 2차원 배열로 구현하면 될 것 같음

 

• 이런 느낌으로 채워가면 될 것 같다 
  1. 내 동전에 맞는 수에 +1
  2. 동전의 배수를 보면서 (동전을 넣었을 때 + 안넣었을 때) 추가하면 될듯

 

풀이

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int coinCnt = Integer.parseInt(st.nextToken());
    int value = Integer.parseInt(st.nextToken());

    int[] arr = new int[value+1];
    int[] coin = new int[coinCnt];

    for (int i =0; i<coinCnt; i++)
      coin[i] = Integer.parseInt(br.readLine());

    for (int i =0; i<coinCnt; i++) {
      int c = coin[i];
      if (value < c)
        continue;

      arr[c]++;

      int tmp = c+1;
      while (tmp <= value) {
        arr[tmp] += arr[tmp-c];
        tmp ++;
      }
    }

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

 

 

 

2294 동전 2 - 골드5

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

2294번: 동전 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 NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int coinCnt = Integer.parseInt(st.nextToken());
    int value = Integer.parseInt(st.nextToken());

    int[] arr = new int[value+1];
    int[] coin = new int[coinCnt];

    for (int i =0; i<coinCnt; i++)
      coin[i] = Integer.parseInt(br.readLine());

    arr[0] = 0;

    for (int i =0; i<coinCnt; i++) {
      int c = coin[i];
      if (value < c)
        continue;

      arr[c] = 1;
      int tmp = c+1;
      while (tmp <= value) {
        if (arr[tmp] == 0) {
          arr[tmp] = arr[tmp-c]+1;
        } else if (arr[tmp-c] != 0) {
          arr[tmp] = Math.min(arr[tmp], arr[tmp-c]+1);
        } 
        
        tmp ++;
      }
    }

    if (arr[value] == 0)
      System.out.println(-1);
    else
      System.out.println(arr[value]);
  }
}

• 애초에 초기값을 Integer.maxvalue로 해뒀으면 0인지 아닌지 확인할 필요도 없었을 것 같다

 

초기값 Integer.maxvalue 풀이

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int coinCnt = Integer.parseInt(st.nextToken());
    int value = Integer.parseInt(st.nextToken());

    int[] arr = new int[value+1];
    int[] coin = new int[coinCnt];

    for (int i =0; i<coinCnt; i++)
      coin[i] = Integer.parseInt(br.readLine());

    for (int i =0; i<arr.length; i++)
      arr[i] = Integer.MAX_VALUE-1;

    for (int i =0; i<coinCnt; i++) {
      int c = coin[i];
      if (value < c)
        continue;

      arr[c] = 1;
      int tmp = c+1;
      while (tmp <= value) {
        arr[tmp] = Math.min(arr[tmp], arr[tmp-c]+1);
        tmp ++;
      }
    }

    if (arr[value] == Integer.MAX_VALUE-1)
      System.out.println(-1);
    else
      System.out.println(arr[value]);
  }
}

• +1을 비교해야하니 max_value -1 을 초기값으로 세팅해줬다

 

• 초기값을 세팅하는 과정이 있지만 매번 0인지 비교하지 않으니 오히려 시간이 줄어듦

 

 

dp 스택이 점점 발전하고있다!