글 읽기 - (C) 백트래킹으로 풀었는데 어디가 틀린지 잘 모르겠습니다.

jakeehoson 3년 전 0

처음엔 브루트 포스로 풀었다가 시간초과나서 백트래킹 방식으로 도전했는데 오히려 채점하자마자 틀렸다고 나옵니다. ㅠㅠ

반례들 찾아보고 직접 만들어보기도 했는데 왜 틀렸는지 잘 모르겠습니다..

고수님들 도와주세요

#include <stdio.h>
#include <stdlib.h>

struct costs{
  int red;
  int green;
  int blue;
};


char colors[3] = {'r', 'g', 'b'};
struct costs* houses;

// path는 실제 지나온 색, lowestpath는 선택마다 가장 비용이 낮은 색
char* path, * lowestpath; 
unsigned int min = 1000001; // 최소 비용
unsigned int cost = 0; // 현재 비용

void find(int depth, int n);
char lowestcolor(struct costs); //가장 낮은 비용의 색을 반환.

int main()
{
  int n;

  scanf("%d", &n);
  houses = (struct costs*)malloc(sizeof(struct costs) * n);
  path = (char*)malloc(sizeof(char) * n + 1);
  lowestpath = (char*)malloc(sizeof(char) * n + 1);

  for (int i = 0; i < n; i++){
    scanf("%d %d %d", &houses[i].red,&houses[i].green,&houses[i].blue);
    lowestpath[i] = lowestcolor(houses[i]);
  }

  find(0, n);

  printf("%d", min);
  

  return 0;
}

void find(int depth, int n){

  int curcost;

  //end check; cost가 min보다 작으면 min 대체
  if (depth == n){
    //printf("cost : %d min : %d\n", cost, min);
    if (cost < min){
      
      min = cost;
      
    }
    return;
  }

  // 만약 가장 비용이 낮은 색이 이전에 선택한 색과 다르고 직후에 가장 비용이 낮은 색과 다르면
  if ((lowestpath[depth] != 't') && lowestpath[depth] != lowestpath[depth+1] && (path[depth - 1] != lowestpath[depth])){
    
    path[depth] = lowestpath[depth];
    if (lowestpath[depth] == 'r'){
      curcost = houses[depth].red;
    }else if(lowestpath[depth] == 'g'){
      curcost = houses[depth].green;
    }else{
      curcost = houses[depth].blue;
    }

    cost += curcost;

    //check
    //printf("depth : %d, %c is unique path.\n",depth, lowestpath[depth]);

    find(depth+1,n);

    cost -= curcost;
    return;
  }

  //이전과 다른 색 두가지 모두 시도.
  for (int i = 0; i < 3; i++){
    if ((path[depth - 1] != colors[i])){

      path[depth] = colors[i];
      
      if (colors[i] == 'r'){
        curcost = houses[depth].red;
      }else if(colors[i] == 'g'){
        curcost = houses[depth].green;
      }else{
        curcost = houses[depth].blue;
      }
      cost += curcost;
        
      //다음 집으로
      find(depth+1,n);

      cost -=curcost;
    }
  }
}

char lowestcolor(struct costs house){
  char low = 'r';
  int count = 0;
  int min = house.red;
  
  if (min > house.green){
    low = 'g';
    min = house.green;
  }
  if (min > house.blue){
    low = 'b';
    min = house.blue;
  }
    
  if (min == house.red){
    count++;
  }
  if (min == house.green){
    count++;
  }
  if (min == house.blue){
    count++;
  }
    
  if ( count >= 2){
    return 't';
  }
  return low;
}

dohoon 3년 전 1

백트로는 시간안에 못 푸는 것으로 압니다.

동적 계획법을 이용해보세요!

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

문제

문제

출처

ICPC

(C) 백트래킹으로 풀었는데 어디가 틀린지 잘 모르겠습니다.

jakeehoson 3년 전 0

dohoon 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말