[JAVA] 백준 dp - 실버모음(11660 구간 합 구하기 5, 2516 포도주 시식, 9465 스티커, 12852 1로 만들기 2)

 

11660 구간 합 구하기 5 - 실버1

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

11660번: 구간 합 구하기 5

 

• 그냥 지정된 범위의 합을 구하면 될 것 같아 이중 for문을 사용하여 더해봤다 -> 시간초과남ㅠ
• 아이디어가 떠오르지 않아서 구글링을 해봤다
• 이 문제는 누적합을 이용하는 문제였다!

 

• 애초에 값을 저장할 때 누적합을 저장했다
• 처음에는 행마다 따로 누적합을 구하는 방식을 사용함
  • xMin, yMin, xMax, yMax가 있다면
  • 원하는 행의 구간합은 arr[i][yMax] - arr[i][yMin] 으로 구할 수 있었고, 원하는 행만큼 반복문을 돌렸다
• 전체 누적값을 구하면 조금 더 시간이 줄어들지 않을까 생각했다
  • 배열에는 좌상부터 우하까지의 누적합을 저장한다
  • 원하는 행,열의 구간합은 arr[xMax][yMax] - arr[xMax][yMin] - arr[xMin][yMax] + arr[xMin-1][yMin-1] 로 구할 수 있다
  • 그림으로 보면 다음과 같다

 

시간비교를 해보면 전체 누적합을 구한 경우가 시간이 조금 덜 걸렸다

행끼리 누적합을 구하면 행에 대해서는 반복문을 돌려야하기 때문에 그런 것 같다.

 

행누적합 풀이

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

    int size = Integer.parseInt(st.nextToken());
    int tcCnt = Integer.parseInt(st.nextToken());
    int[][] arr = new int[size][size];

    for (int i =0; i<size; i++) {
      st = new StringTokenizer(br.readLine());
      int buffer = 0;
      for (int j =0; j<size; j++) { //가로 누적합 구하기
        buffer += Integer.parseInt(st.nextToken());
        arr[i][j] = buffer;
      }
    }

    for (int tc=0; tc<tcCnt; tc++) {
      st = new StringTokenizer(br.readLine());
      int xMin = Integer.parseInt(st.nextToken())-1;
      int yMin = Integer.parseInt(st.nextToken())-1;
      int xMax = Integer.parseInt(st.nextToken())-1;
      int yMax = Integer.parseInt(st.nextToken())-1;

      if (xMin > xMax) {
        int tmp = xMin;
        xMin = xMax;
        xMax = tmp;
      }

      if (yMin > yMax) {
        int tmp = yMin;
        yMin = yMax;
        yMax = tmp;
      }

      int result = 0;
      for (int i = xMin; i <= xMax; i++) {
        result += arr[i][yMax];
        if (yMin -1 >= 0)
          result -= arr[i][yMin-1];
      }

      sb.append("" + result + "\n");
    }

    System.out.print(sb);
  }
}

 

전체 누적합 풀이(Good)

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

    int size = Integer.parseInt(st.nextToken());
    int tcCnt = Integer.parseInt(st.nextToken());
    int[][] arr = new int[size][size];

    for (int i =0; i<size; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j =0; j<size; j++) { //전체 누적합 구하기
        int sum = Integer.parseInt(st.nextToken());
        if (j != 0)
          sum += arr[i][j-1];
        if (i != 0)
          sum += arr[i-1][j];
        if (i != 0 && j != 0)
          sum -= arr[i-1][j-1];

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

    for (int tc=0; tc<tcCnt; tc++) {
      st = new StringTokenizer(br.readLine());
      int xMin = Integer.parseInt(st.nextToken())-1;
      int yMin = Integer.parseInt(st.nextToken())-1;
      int xMax = Integer.parseInt(st.nextToken())-1;
      int yMax = Integer.parseInt(st.nextToken())-1;

      if (xMin > xMax) {
        int tmp = xMin;
        xMin = xMax;
        xMax = tmp;
      }

      if (yMin > yMax) {
        int tmp = yMin;
        yMin = yMax;
        yMax = tmp;
      }

      int result = arr[xMax][yMax];
      if (xMin != 0)
        result -= arr[xMin-1][yMax];
      if (yMin != 0)
        result -= arr[xMax][yMin-1];
      if (xMin != 0 && yMin != 0)
        result += arr[xMin-1][yMin-1];

      sb.append("" + result + "\n");
    }

    System.out.print(sb);
  }
}

 

 

 

2516 포도주 시식 - 실버1

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

2156번: 포도주 시식

 

• 각 포도주를 먹는경우, 안먹는 경우를 비교하여 최대양을 고를 생각이다
• 행은 각 포도주이고, 열은 포도주 개수로 하면 될 것 같다
• 세 번째 포도주를 먹는 경우는 (1)첫 번째 포도주를 안먹는 경우 최댓값 (2)두 번째 포도주를 안먹는 경우 최댓값   두 가지 경우 중 최댓값을 선택하면 될 것 같다
• 점화식은 max( arr[i-1][j-1] , arr[i-1][j-2] )

 

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

    int cnt = Integer.parseInt(br.readLine());
    int[] amount = new int[cnt];
    for (int i =0; i<cnt; i++)
      amount[i] = Integer.parseInt(br.readLine());

    int[][] arr = new int[cnt][2];

    for (int i= 0; i<arr.length; i++) {
      int caseEat = amount[i];
      int caseNotEat = 0;

      if (i >= 2) {
        caseNotEat = Math.max(arr[i - 1][0], arr[i - 1][1]);

        int eatNotEat = arr[i-2][1] + amount[i-1];
        int notEatEat = Math.max(arr[i-2][0], arr[i-2][1]);

        caseEat += Math.max(eatNotEat , notEatEat);

      } else if (i == 1) {
        caseNotEat = Math.max(arr[i - 1][0], arr[i - 1][1]);
        caseEat += Math.max(arr[i - 1][0], arr[i - 1][1]);
      }

      arr[i][0] = caseEat;
      arr[i][1] = caseNotEat;
    }

    System.out.print(Math.max(arr[cnt-1][0], arr[cnt-1][1]));
  }
}

 

 

9465 스티커 - 실버1

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

9465번: 스티커

 

• 스티커를 떼는 경우와 안떼는 경우를 이용해 2차원 배열에 값을 저장하면 될 것 같았다
• 그런데 방향이 너무 헷갈렸다.. 행우선으로 채울 경우 위와 왼쪽을 모두 고려하기엔 둘은 같은 상황이 아니었음 (위의 경우 그 옆 행을 고려하지 않은 경우이고, 왼쪽의 경우 자신의 윗 행을 모두 고려한 경우였음)
• 고민하다 시간을 너무 많이 써서 결국 구글링을 해봤다

 

오타: 놓고 -> 떼고

• 2 x n 배열이기 때문에 특수한 상황이라 가능한 건지는 모르겠지만, 채울 때 한 쪽 방향만 고려하면 됐다
• 열우선으로 채운다고 가정했을 때, 사진의 별 부분의 값은 (1)나를 뗄 때 (2)나를 안뗄 때를 비교하여 max값을 넣어주면 된다
  • (1)나를 뗄 때 = 1을 떼고 + 2을 안떼고 + 나를 뗌 = 1을 떼고 + 나를 뗌 (1을 뗄 수 있으면 2는 못 뗌)
  • (2)나를 안 뗄 때 = 1을 안떼고 + 2를 뗄 수 있음 = 2를 뗄 수 있는 경우
• 배열을 채우는 방향만 잘 생각했으면 어렵지 않은 문제였다

 

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

    int tcCnt = Integer.parseInt(br.readLine());

    StringBuilder sb = new StringBuilder();
    for (int tc = 0; tc < tcCnt; tc++) {
      int colCnt = Integer.parseInt(br.readLine());
      int[][] arr = new int[2][colCnt];

      for (int i = 0; i < 2; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int j = 0; j < colCnt; j++)
          arr[i][j] = Integer.parseInt(st.nextToken());
      }

      for (int i = 1; i < colCnt; i++) {
        arr[0][i] = Math.max(arr[0][i - 1], arr[1][i - 1] + arr[0][i]);
        arr[1][i] = Math.max(arr[0][i - 1] + arr[1][i], arr[1][i - 1]);
      }

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

    System.out.print(sb);
  }
}

• 2xn배열을 만들고
• i-1 열의 값을 통해 내 값을 구했다

 

 

 

12852 1로 만들기 2 - 실버1

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

12852번: 1로 만들기 2

 

• 이전에 비슷한 문제를 푼 기억이 난다! (1로 만들기 였던걸로 기억한다)
• 그 문제와 차이점은 기록을 남긴다는 것이었다
• 백트래킹으로 할 때는 visited 스택을 만들어 (1)push (2)dfs()재귀 (3)pop 해주는 식으로 결과를 저장해도 될 것 같다
• dp의 경우 각 배열값에 경로를 저장하면 메모리 초과가 날 것 같아서 다른 생각을 떠올렸다
  • 각 배열에 이전값(prev)을 저장하여 최소연산일 때 내 이전값을 알 수 있도록 하는 걸 생각했다
  • 1부터 재귀호출로 이전값을 부른다면 최소연산일 때 기록을 찾아낼 수 있다

 

백트래킹 풀이

public class Main {
  static Stack<Integer> stack = new Stack<>();
  static List<Integer> result;
  static int min = Integer.MAX_VALUE;
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int num = Integer.parseInt(br.readLine());

    stack.push(num);
    dfs(num, 0);

    StringBuilder sb = new StringBuilder();
    sb.append(min + "\n");

    for (int i: result)
      sb.append(i + " ");

    System.out.print(sb);
  }

  private static void dfs(int num, int cnt) {
    if (num == 1) {
      if (min > cnt) {
        result = new ArrayList<>();
        result.addAll(stack);
        min = cnt;
      }

      return;
    }

    if (cnt > min)
      return;

    if (num%3 == 0) {
      stack.push(num/3);
      dfs(num/3, cnt+1);
      stack.pop();
    }

    if (num%2 == 0) {
      stack.push(num/2);
      dfs(num/2, cnt+1);
      stack.pop();
    }

    if (num - 1 > 1) {
      stack.push(num-1);
      dfs(num-1, cnt+1);
      stack.pop();
    }
  }
}

• 지금까지의 기록을 stack에 저장한다
• 최소 연산을 찾았을 경우에는 result에 stack값을 넣어 저장한다
• 재귀가 끝난 후에는 기록에서 나를 뺀다 (pop)

 

 

dp풀이

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

    int[][] arr = new int[num+1][2];
    arr[num][0] = 0;    //초기화
    arr[num][1] = num;

    for (int i = num-1; i>=1; i--) {
      int cnt = arr[i+1][0] + 1;
      int prev = i+1;

      if (i*3 <= num && arr[i*3][0] + 1 < cnt) {
        cnt = arr[i*3][0] + 1;
        prev = i*3;
      }

      if (i*2 <= num && arr[i*2][0] + 1 < cnt) {
        cnt = arr[i*2][0] + 1;
        prev = i*2;
      }

      arr[i][0] = cnt;
      arr[i][1] = prev;
    }

    List<Integer> list = new ArrayList<>();
    int idx = 1;
    while (true) {
      list.add(idx);
      if (idx == num)
        break;
      idx = arr[idx][1];
    }

    StringBuilder sb = new StringBuilder();
    sb.append(arr[1][0] + "\n");

    for (int i =list.size()-1; i>=0; i--)
      sb.append(list.get(i) + " ");

    System.out.print(sb);
  }
}

• num+1 길이의 일차원 배열을 만들었다고 생각하면 편할듯
• 각 배열값에는 현재 수를 만들기 위한 최소연산 수와 prev값이 저장됨
• 세 가지 경우를 비교하여 최소연산수를 저장한다
  • num*3 값 +1    /    num*2 값 + 1    /    num+1값 + 1  
  • prev값도 같이 저장해준다
• 저장된 배열에서 1부터 prev를 재귀적으로 찾아간 후, reverse한 값을 출력한다

 

 

성능비교

• dp가 백트래킹보다 2배이상 시간이 빠르다
  • 백트래킹이 가지치기가 잘 되어 더 빠를 줄 알았는데 아니였음
• 대신 메모리를 3배이상 씀
• dp를 사용할 수 있는 범위라면 dp를 쓰는게 확실히 빠른 것 같다

 

 

 

 

 

 

 

 

 

교훈: dp는 많이 풀어보자!