글 읽기 - [스포] dp문제라서 dp로 풀었는데.. 허탈하네요

ynifamily3 4년 전 2

단순히 N*M-1 만 하면 풀리네요 아이고

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <string>
#include <set>

using namespace std;

int N, M;
//  NxM사이즈의 초콜릿을 자를 때, 최소 횟수로 완전 분해할수 있는 횟수.
int choco[301][301];

int get_choco(int _N, int _M) {
  if (_N == 1) return _M - 1;
  if (_M == 1) return _N - 1;
  if (choco[_N][_M] != -1) return choco[_N][_M];

  return choco[_N][_M] = 1 + get_choco(_N/2, _M) + get_choco(_N/2, _M) + (_N % 2) + (_N % 2) * (_M - 1);
}
// 4 * 10 => (2 * 5)
// N * M 을 자를 때
// 2 * 3
// o o o
// o o o
// 최소횟수 5회.
// 어떻게 자르든지 최소가 될거같은데?
// 계산량 최소화 하려면 되도록 중앙에서 자르는 것이 좋을 듯.

int main() {
  cin >> N >> M;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      choco[i][j] = -1;
    }
  }
  // 목표: choco[N][M] 값 구하기
  cout << get_choco(N, M) << endl;
  return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[스포] dp문제라서 dp로 풀었는데.. 허탈하네요

ynifamily3 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말