글 읽기 - 왜 틀렸는지 모르겠습니다..

rlrlacodnjs 7년 전 0

완전 초보입니다.. 좀 도와주세요!

#include<stdio.h>
int main(){
  int k =0;
  int n=0;
 scanf("%d",&k);
  if(k<1 || k>1000000)
      return -1;
  while(k!=1){
  if(!(k%3)){
   k=k/3;
      n++;
  }
      else if(!((k-1)%3)){
          k=k-1;
          n++;
           k=k/3;
      n++;
          
      }
  else if(!(k%2))
  {
      k=k/2;
    n++;
  }
        else if(!((k-1)%2)){
          k=k-1;
          n++;
           k=k/2;
      n++;
          
      }
      else{
            k=k-1;
  n++;
      }

  }
  printf("%d",n);
    return 0;
}

toysmars 7년 전 1

이 휴리스틱은 모든 경우를 다 커버할 수 없습니다.

예를 들어 입력이 16일때, 이 휴리스틱은 16, 15, 5, 4, 2, 1 의 순으로 해를 찾는데, 더 좋은 해는 16, 8, 4, 2, 1 이 있죠.

사실 이 문제를 커버할 수 있는 그리디 알고리즘이 있는지 의문이구요.

대부분의 문제가 문제를 정확히 풀려면 모든 가능한 경우를 (중복을 피해서) 다 따져봐야 하는데, 이 문제의 경우 BFS로 해결 가능합니다.

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다..

rlrlacodnjs 7년 전 0

toysmars 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말