[SWEA][C++] 9282: 초콜릿과 건포도

문제 링크: 링크

 

오랜만에 알고리즘 공부를 하려니 좀이 쑤시네요;;

SW Expert Academy(SWEA) 9282번을 풀어보겠습니다. 난이도는 D4입니다.

그냥 풀이만 간단하게 올리겠습니다.

 

일단 이 문제는 2009년 IOI(국제 정보올림피아드) 4번 문제 'Raisins(건포도)' (백준 링크) 와 동일합니다.

초콜릿에 자를 대고 자를 수 있고, 자를 때마다 자르기 전 초콜릿에 있는 건포도만큼을 요금으로 냅니다.

n x m 사이즈 초콜릿을 1 x 1 조각들로 나누는데 드는 최소한의 요금을 구하는 게 문제입니다.

 

예를 들어 \( \begin{matrix} 2 & 7 & 5 \\ 1 & 9 & 5 \end{matrix} \) 모양을 가진 초콜릿이 있을 때, 위 순서대로 자르면 77의 비용이 나오고 이게 최소 비용입니다.

 

\[ cost(초콜릿) \\ = min \Biggl( \{ cost(x)+cost(y)+sum(초콜릿) | \text{x와 y는 초콜릿을 자른 두 조각} \} \Biggr) \]

해결방법은 dp(memoization)와 prefix sum입니다. 위 수식을 맞게 표현한건지 잘 모르겠네요;;

위 수식에서 sum은 자르기 전의 초콜릿 위에 있는 건포도를 다 더한겁니다.

 

자른 초콜릿의 최소 cost는 언제나 동일합니다. 그리고 잘린 초콜릿 조각끼리 서로 영향을 주지 않으니 최적 부분 조건이 성립합니다.

자르는 방법은 재귀적으로 다 잘라보시면 됩니다. 이 때 memoziation을 사용해야 계산 횟수를 줄일 수 있습니다.

 

자르기 전 건포도 개수를 다 더할 때(sum) 매 번 구하면 시간 초과가 나오니 2d array prefix sum을 사용해야 합니다. 포함배제 원칙 생각해서 만들면 됩니다.

 

아래는 소스입니다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

const int INF = 987654321;
const int MAX_LEN = 51;

//y, x, width, height
int cache[MAX_LEN][MAX_LEN][MAX_LEN][MAX_LEN];
int chocolate[MAX_LEN][MAX_LEN];
int subsum[MAX_LEN][MAX_LEN];

int raisin_sum(int y, int x, int width, int height) {
  const int& y2 = y+height-1, x2=x+width-1, y1=y, x1=x;

  return subsum[y2][x2]
    - subsum[y2][x1-1]
    - subsum[y1-1][x2]
    + subsum[y1-1][x1-1];
}

int raisin(int y, int x, int width, int height) {
  //base
  if (width == 1 && height == 1) return 0;

  int& ret = cache[y][x][width][height];
  if (ret != -1) return ret;
  ret = INF;

  //가로로 자르기
  for (int cut_height = 1; cut_height < height; ++cut_height) {
    ret = min(
      ret,
      raisin(y, x, width, cut_height) + raisin(y+cut_height, x, width, height-cut_height) + raisin_sum(y, x, width, height)
    );
  }

  //세로로 자르기
  for (int cut_width = 1; cut_width < width; ++cut_width) {
    ret = min(
      ret,
      raisin(y, x, cut_width, height) + raisin(y, x+cut_width, width-cut_width, height) + raisin_sum(y, x, width, height)
    );
  }

  return ret;
}


int main(int argc, char** argv)
{
  freopen("input.txt", "r", stdin);

  int test_case;
  int T;
  int n, m;

  cin >> T;


  for (test_case = 1; test_case <= T; ++test_case)
  {
    memset(cache, -1, sizeof(cache));
    memset(subsum, 0, sizeof(subsum));

    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        cin >> chocolate[i][j];
      }
    }


    //부분합 구하기
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        subsum[i][j] = (j == 0 ? chocolate[i][j] : subsum[i][j - 1] + chocolate[i][j]);
  
    for (int i = 1; i < n; ++i)
      for (int j = 0; j < m; ++j)
        subsum[i][j] = subsum[i - 1][j] + subsum[i][j];

    cout << "#" << test_case << " " << raisin(0, 0, m, n) << "\n";
  }

  return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

백준이랑 똑같은 문제라서 조금만 수정해서 올리려고 했더니 wrong answer가 나오네요. 왜지?.. ㅠㅠ

 

+ 2020. 07. 01

드디어 알아냈습니다. 누적합으로 (y,x) ~ (y+height, x+width)에 있는 건포도 계산할 때 x1>0, y1>0을 체크해줘야 합니다. 아니 근데 이러면 메모리 이상한거 찍은거니까 런타임에러를 뿜어야 맞는거 아닌가... 정말 삽질했습니다 휘유