글 읽기 - DFS, 메모이제이션 관련 알고리즘 최적화 질문입니다.

creationyun 5년 전 0

시간 초과가 뜨긴 하지만, 아무리 생각해봐도 DFS+메모이제이션(map) 밖에는 더 최적화할 방법이 떠오르지 않네요.

그렇다고 다이나믹 프로그래밍으로 해결하기에는 각 스킬마다 쓸 수 있는 마나 리스트(skMana)를 배열/벡터로 다 저장해야 해서 저장공간이 많이 필요한데...

어떻게 하면 좋을까요?

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

/*
D[remHp, {mana0, mana1, ..., mana(n-1)}]
= min{ D[remHp-attk(i), {mana0, mana1, ..., mana(i)+k, ..., mana(n-1)}] + mana(i) }
(i = 0, 1, 2, ..., n-1)
(remHp >= attk(i))

D[0, all] = 0
*/

using namespace std;

int skill, manaInc;
int skAttk[101] = {};
map<pair<int, vector<int>>, int> dp;

int checking(int remHp, vector<int> skMana)
{
  if (remHp < 0) return -1;
  if (remHp == 0) {
    return 0;
  }
  if (dp.find({remHp, skMana}) != dp.end()) {
    return dp[{remHp, skMana}];
  }
  vector<int> newSkMana;

  int result = 2100000000;
  int calc;
  for (int i = 0; i < skill; i++) {
    newSkMana = skMana;
    newSkMana[i] += manaInc;

    calc = checking(remHp-skAttk[i], newSkMana) + skMana[i];
    if (calc == -1 + skMana[i]) continue;
    if (result > calc) {
      result = calc;
      dp[{remHp, skMana}] = calc;
    }
  }
  return result;
}

int main()
{
  int health;
  vector<int> skMana;
  cin >> skill >> health >> manaInc;
  for (int i = 0; i < skill; i++) {
    int mpt;
    cin >> mpt;
    skMana.push_back(mpt);
    cin >> skAttk[i];
  }

  cout << checking(health, skMana) << endl;

  return 0;
}

messi 5년 전 0

다이나믹 프로그래밍을 어떻게 생각하셨는지는 모르겠는데

i번 스킬까지만 사용하여 j만큼 피를 깎는데 필요한 최소비용을 생각하면 될 것 같네요

어차피 최대 피는 100이고 스킬도 100개밖에 안돼서 메모리는 충분하네요

creationyun 5년 전 0

그러면 스킬을 쓸 때마다 그 스킬의 마나가 변하는데 어떻게 처리해야 하나요?

creationyun 5년 전 0

아! 해결됐습니다. 힌트 주셔서 감사합니다!

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

문제

문제

출처

ICPC

DFS, 메모이제이션 관련 알고리즘 최적화 질문입니다.

creationyun 5년 전 0

messi 5년 전 0

creationyun 5년 전 0

creationyun 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말