글 읽기 - c++) 고수님들 도와주세요 쉽습니다

woogie 3년 전 0

백트래킹 이용해서 순서 값을 찍었을때 가장 작은값이 순서대로 나오는것을 확인했는데

출력하니까 1차이로 답이 틀리네요

도저히 이유를 모르겠습니다

도와주세요 ㅠㅅㅠ

#include<iostream>

#define MAX 1000

using namespace std;

int N;
int person[MAX];
int copy_person[MAX];
int check[MAX];
int ret = 99999;

void solution(int cnt) {

  int sum = copy_person[0];

  if(cnt==N) {
    //어디가 틀렸는지 모르겠습니다........
    for (int i=1; i<N; i++) {
		  copy_person[i] = copy_person[i - 1] + copy_person[i];
		  sum += copy_person[i];
	  }

    if(ret>sum) {
      ret = sum;
    }
  
    return;
  }
  for(int i=0; i<N; i++) {
    if(!check[i]) {
      copy_person[cnt] = person[i];       
      check[i] = 1;
      solution(cnt+1);
      check[i] = 0;
    }
  }
}

int main() {

  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  
  for(int i=0; i<N; i++) {
    cin >> person[i];
  }

  solution(0);

  cout << ret << endl;

  return 0;
}

gurugeonu 3년 전 1

인출 시간이 짧은 순서대로 사람들을 정렬한 후 각 사람의 시간을 모두 합하면 풀립니다

woogie 3년 전 0

백트래킹으로 풀어보고 싶었습니다!

순열을 이용해서 풀어봤는데

인출시간이 짧은 순서대로 나온 경우가 있었습니다. 근데

값이 틀리게 나온 이유 알수있을까요?

woogie 3년 전 0

copy_person이 계속 변하기 때문인걸 인지하지 못했습니다 ㅠ

따라서 초기에 배열을 한번 더 복사해서 풀었습니다.

코드는 다음과 같습니다.

#include<iostream>

#define MAX 1000

using namespace std;

int N;
int person[MAX];
int copy_person[MAX];
int check[MAX];
int ret = 99999;

void solution(int cnt) {

  int sum = 0;

  if(cnt==N) {

    int copy_person2[N];

    for (int i=0; i<N; i++) {

      copy_person2[i] = copy_person[i];
      cout << copy_person2[i] << ' ';
    }
    for (int i=0; i<N; i++) {
      copy_person2[i] = copy_person2[i-1] + copy_person2[i];
      sum += copy_person2[i]; 
    }

    cout << " sum : " << sum << endl;

    if(ret>sum) {
      ret = sum;
    }
	  
    cout << ret << endl;

    return;
  }
  for(int i=0; i<N; i++) {
    if(!check[i]) {
      copy_person[cnt] = person[i];       
      check[i] = 1;
      solution(cnt+1);
      check[i] = 0;
    }
  }
}

int main() {

  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  
  for(int i=0; i<N; i++) {
    cin >> person[i];
  }

  solution(0);

  cout << ret << endl;

  return 0;
}

gurugeonu 3년 전 1

백트래킹으로 푸시면 아마 시간초과가 나실 겁니다. 굳이 백트래킹으로 하신다면 두번째 코드에서 26~29번째줄 for문을 마이너스 인덱스에 접근하지 않게 해야할 것 같습니다.

#include<iostream>

#define MAX 1000

using namespace std;

int N;
int person[MAX];
int copy_person[MAX];
int check[MAX];
int ret = 99999;

void solution(int cnt) {

  int sum = 0;

  if(cnt==N) {

    int copy_person2[N];

    for (int i=0; i<N; i++) {

      copy_person2[i] = copy_person[i];
      cout << copy_person2[i] << ' ';
    }
    //이렇게 하면 i가 0일때 마이너스 인덱스에 접근하게 됩니다
    /*for (int i=0; i<N; i++) {
      copy_person2[i] = copy_person2[i-1] + copy_person2[i];
      sum += copy_person2[i]; 
    }*/
      
    //수정한 코드
    sum += copy_person2[0];
    for (int i = 1; i < N; i++) {
      copy_person2[i] = copy_person2[i-1] + copy_person2[i];
      sum += copy_person2[i];
    }

    cout << " sum : " << sum << endl;

    if(ret>sum) {
      ret = sum;
    }
	  
    cout << ret << endl;

    return;
  }
  for(int i=0; i<N; i++) {
    if(!check[i]) {
      copy_person[cnt] = person[i];       
      check[i] = 1;
      solution(cnt+1);
      check[i] = 0;
    }
  }
}

int main() {

  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  
  for(int i=0; i<N; i++) {
    cin >> person[i];
  }

  solution(0);

  cout << ret << endl;

  return 0;
}

woogie 3년 전 0

지적과 좋은 답변 감사합니다 !

midascha 2년 전 2

쉬운 문제는 쉽게 풀이하는게 최고인듯 합니다.

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

문제

문제

출처

ICPC

c++) 고수님들 도와주세요 쉽습니다

woogie 3년 전 0

gurugeonu 3년 전 1

woogie 3년 전 0

woogie 3년 전 0

gurugeonu 3년 전 1

woogie 3년 전 0

midascha 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말