글 읽기 - 시간 초과 이유

wildvine09 2년 전 0

비트마스크 + dp 로 O(N*2^N) 코드를 만들어 냈는데 왜 시간 초과가 날까요..?

N=16에서 O(N*2^N) 이면 시간제한 안에는 해결이 될 텐데...

초기에 켜진 발전소 개수>p 인 경우에 무한루프 돌다가 재귀가 뻗어 버리는 경우도 고려해서 짰는데...

#include <stdio.h>

int dp[1<<16], arr[17][17], p, n, state, counter;
char c;
//arr[i][j]: i번째를 이용해서 j번째를 켜는 데 드는 비용
int f(int x, int y){
  if(y>=p){
    return 0;
  }
  if(dp[x]!=0) return dp[x];
  int min=99999999, min2;
  for(int i=0; i<n; i++){
    if(!(x & (1<<i))){
      min2=99999999;
      for(int j=0; j<n; j++){
        if(x & (1<<j)){
          min2=(min2>arr[j][i] ? arr[j][i]:min2);
        }
      }
      x+=(1<<i);
      int k=f(x, y+1)+min2;
      min=(min>k ? k:min);
      x-=(1<<i);
    }
  }
  return dp[x]=min;
}

int main() {
  scanf("%d", &n);
  for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d", &arr[i][j]);
  for(int i=0; i<n; i++){
    scanf(" %c", &c);
    if(c=='Y'){
      state+=(1<<i);
      counter++;
    }
  }
  scanf("%d", &p);
  if(counter==0){
    if(p==0) printf("0");
    else printf("-1");
    return 0;
  }
  printf("%d", f(state, counter));
}

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

문제

문제

출처

ICPC

시간 초과 이유

wildvine09 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말