글 읽기 - [C++] 56%에서 틀렸다고 나오는데, 문제점을 찾지 못하겠습니다.

boxer1532 2년 전 0

안녕하세요! 해당 문제를 bfs를 통해 풀려고 시도해보았습니다.

예제 tc들을 모두 통과하여 제출하였더니, 56%에서 '틀렸습니다' 판정을 받았습니다.

이에, 질문 게시판을 검색하던 중 아래 세 가지 tc들에 대해 오답을 출력하는 것을 확인하였지만,

계속 고민해봐도 무엇이 문제인지 찾지 못하겠습니다.

4 1 4 4 4 4 3 2 2 4 -> 205

5 3 2 5 2 4 4 2 4 1 -> 231

5 4 5 2 2 2 5 3 1 4 -> 245

(https://www.acmicpc.net/board/...)

제 logic 중에 무엇이 문제인지 찾아주시면 감사하겠습니다!

긴 글 읽어주셔서 감사합니다 :)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <vector>

using namespace std;

int kgt[5][2] = {0}; // [0]: 위치, [1]: 종류 (0: 외곽, 1: 10~19사이, 2: 20~24사이, 3: 30~26사이, 4:25~40사이)
int dice[15] = {0};
int ans = 0;
int cur_type;

int move_operation(int pos, int k_type, int move_value){
  int res_pos = pos;

  if(k_type == 0){ // 0: 외곽
    res_pos = res_pos + 2*move_value;
	cur_type = 0;

	if(res_pos == 10)
      cur_type = 1;
	else if(res_pos == 20)
	  cur_type = 2;
	else if(res_pos == 30)
	  cur_type = 3;
	else if(res_pos == 40)
	  cur_type = 4;
  }
  else if(k_type == 1){ // 1: blue 10~19
	cur_type = 1;
    for(int k=0; k<move_value; k++){
	  if(res_pos < 19)
	    res_pos += 3;
	  else if(res_pos == 19){
	    res_pos = 25;
		cur_type = 4;
	  }
	  else
	    res_pos += 5;
	}
  }
  else if(k_type == 2){ // 2: blue 20~24
	cur_type = 2;
    for(int k=0; k<move_value; k++){
	  if(res_pos < 24)
	    res_pos += 2;
	  else if(res_pos == 24){
	    res_pos = 25;
		cur_type = 4;
	  }
	  else
	    res_pos += 5;
	}
  }
  else if(k_type == 3){ // 3: blue 30~26
	cur_type = 3;
    for(int k=0; k<move_value; k++){
	  if(res_pos == 30)
	    res_pos = 28;
	  else if(res_pos == 27 || res_pos == 28)
	    res_pos -= 1;
	  else if (res_pos == 26) {
		  res_pos = 25;
		  cur_type = 4;
	  }
	  else
	    res_pos += 5;
	}
  }
  else if(k_type == 4){ // 4: center 25~40
	cur_type = 4;
    res_pos = res_pos + 5*move_value;
  }

  return res_pos;
}

void solve(int dice_idx, int move_kgt, int cur_score){
  if(dice_idx == 10){
    ans = max(ans, cur_score);
	return;
  }

  if(kgt[move_kgt][0] > 40)
    return;

  int cur_dice = dice[dice_idx];
  int move_pos = move_operation(kgt[move_kgt][0], kgt[move_kgt][1], cur_dice);

  for(int i=1; i<=4; i++){
    if(move_pos <= 40 && i!=move_kgt && kgt[i][0]==move_pos && kgt[i][1]==cur_type)
	  return;
  }

  kgt[move_kgt][0] = move_pos;
  kgt[move_kgt][1] = cur_type;

  if(move_pos > 40)
    move_pos = 0;

  int ori_pos, ori_type;

  // 1번말 이동
  ori_pos  = kgt[1][0];
  ori_type = kgt[1][1];
  solve(dice_idx + 1, 1, cur_score + move_pos);
  kgt[1][0] = ori_pos;
  kgt[1][1] = ori_type;

  // 2번말 이동
  ori_pos  = kgt[2][0];
  ori_type = kgt[2][1];
  solve(dice_idx + 1, 2, cur_score + move_pos);
  kgt[2][0] = ori_pos;
  kgt[2][1] = ori_type;

  // 3번말 이동
  ori_pos  = kgt[3][0];
  ori_type = kgt[3][1];
  solve(dice_idx + 1, 3, cur_score + move_pos);
  kgt[3][0] = ori_pos;
  kgt[3][1] = ori_type;

  // 4번말 이동
  ori_pos  = kgt[4][0];
  ori_type = kgt[4][1];
  solve(dice_idx + 1, 4, cur_score + move_pos);
  kgt[4][0] = ori_pos;
  kgt[4][1] = ori_type;

  return;
}

int main(){
  for(int i=0; i<10; i++)
    scanf("%d", &dice[i]);

  // 1번 말
  memset(kgt, 0, sizeof(kgt));
  cur_type = 0;
  solve(0, 1, 0);

  // 2번 말
  memset(kgt, 0, sizeof(kgt));
  cur_type = 0;
  solve(0, 2, 0);

  // 3번 말
  memset(kgt, 0, sizeof(kgt));
  cur_type = 0;
  solve(0, 3, 0);

  // 4번 말
  memset(kgt, 0, sizeof(kgt));
  cur_type = 0;
  solve(0, 4, 0);

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

boxer1532 2년 전 0

자답하겠습니다.

57~71 line에서 blue arrow (26~30) 구간을 처리하는 과정에서

center에 있는 30과 outside에 있는 30을 구분하지 않아서 '틀렸습니다' 판정을 받았었습니다.

두 30을 구분해서 '맞았습니다' 판정 받았습니다.

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

문제

문제

출처

ICPC

[C++] 56%에서 틀렸다고 나오는데, 문제점을 찾지 못하겠습니다.

boxer1532 2년 전 0

boxer1532 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말