글 읽기 - 9%에서 틀리는데 반례 부탁드립니다.

woodylyw 2년 전 0

DFS로 A 숫자들로 만들 수 있는 순열을 다 만들어보고 B보다 작은 경우중 가장 큰수를 만들었습니다.

예제는 정상적으로 출력되는데 반례를 찾을 수가 없네요.

반례 좀 부탁드리겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

bool visited[10]={0,};
int array[10]= {0,};
int nums[10] = {0,};
int A, B;
int MAX=-1;
void dfs(int cnt, int M){
  if(cnt==M){
    int new_case = 0;
    if(nums[array[M-1]]==0) return; // 맨앞자리 0인 경우 제외.
    for(int i=0; i<M; i++){
      new_case += nums[i] * std::pow(10,array[i]);
    }
    if(new_case > MAX && new_case < B)
      MAX = new_case;
    return;
  }
  
  for(int i=0; i<M; i++){
    if(!visited[i]){
      array[cnt] = i;
      visited[i]=true;
      dfs(cnt+1, M);
      visited[i]=false;
    }
  }
}
int main()
{
  std::cin>>A>>B;
  
  int cnt=0;
  while(A!=0){
    nums[cnt]=A%10;
    A/=10;
    cnt++;
  }
  int sizeA = cnt;
  dfs(0,sizeA);
  
  std::cout<<MAX;
  return 0;
}

azberjibiou 2년 전 1

앞자리가 0인 경우를 제외하는 부분과 new_case를 확인하는 부분을 잘 살펴보세요~

woodylyw 2년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

9%에서 틀리는데 반례 부탁드립니다.

woodylyw 2년 전 0

azberjibiou 2년 전 1

woodylyw 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말