글 읽기 - 재귀형식의 구현 실패 질문

traveler22 1년 전 0

데이터는 node, edge 모두 index 0~N-1 사이에 저장했으며,

void solve(int lo, int hi)는 [lo, hi)의 node들을 고려하여 그리디알고리즘을 적용하고 있습니다.

맨 마지막 hi번째 index는 포함하나, 연산에는 전혀 사용되지 않는 모습을 보입니다.

(ex : node[4] = {1,2,3,4}일 때, node[3]=4는 연산에 전혀 사용되지 않는 것처럼 solve함수에서도 배제하는 모습 찾을 수 있습니다)

17점이 뜬 것으로 미루어보아 재귀형 구현의 단점인 스택 오버플로우 문제는 아닌 것 같아 이렇게 질문드려봅니다.

좋은 답변 주신다면 감사하겠습니다.

#include <iostream>
#include <vector>
#define ll long long 
using namespace std;
int N;
vector<ll> node(100000);
vector<ll> edge(100000); //node[N-1]-edge[N-1]-node[N]
ll res;
void solve(int lo, int hi){ //node[lo] ~ node[hi-1] 중 최소값 search 후 재귀반환
  //cout << lo << ' ' << hi << ' ';
  if (lo>=hi) return;
  
  int mmin = lo;
  for(int i = lo+1; i < hi-1; ++i){
    if (node[i] <= node[mmin]) mmin = i;
  }
  ll tmp = 0;
  for(int i = mmin; i <= hi - 1; ++i){
    tmp += edge[i];
  }  
  res += tmp * node[mmin];
  //cout << node[mmin] << endl;
  //cout << tmp << endl;
  return solve(lo, mmin);
}

int main(void){
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  
  cin >> N;
  for(int i = 0; i < N-1; ++i){
    cin >> edge[i];
  }
  for(int i = 0; i < N; ++i){
    cin >> node[i];
  }
  /*
  for(int i = 0; i < N; ++i){
    cout << node[i] << edge[i] << endl;
  }*/
  solve(0,N-1);
  cout << res << endl;
  return 0;
}

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

문제

문제

출처

ICPC

재귀형식의 구현 실패 질문

traveler22 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말