글 읽기 - 왜 시간초과가 나는지 모르겠네요.

pch6789 2년 전 0

어디를 개선해야하는지 도저히 모르겠습니다. ㅠ
지금 2일째 도전중인데 더는 개선방향을 못잡겠습니다.
도와주시면 감사하겠습니다.

알고리즘은
가장 많은 블럭을 차지하는 숫자부터 넣어보도록 되어있습니다.
이후 만약 더 사전순으로 먼저 오도록 될 경우 답을 변경하도록 되어있습니다.

각 실행별로 실재로 값을 기록했다 지우는 과정을 넣었습니다.
97%에서 멈추네요 ㅠ

#include <iostream>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>

using namespace std;
vector<pair<int, int>> st[6];
pair<int, int> startPoint = {0, 0};
vector<pair<int, char>> pieceSize(6, {0, 0});

bool findAnswer = false;
vector<string> answer;
int callCnt = 0;
void backtracking(int idx, vector<string> paper, int x, int y, int count)
{
  callCnt++;
  char numberC = pieceSize[idx].second;
  int number = numberC - '0';
  auto p1 = st[number][0];
  if (x + p1.first >= paper.size())
  {
    return;
  }
  if (y + p1.second >= paper.size())
  {
    backtracking(idx, paper, x + 1, 0, count);
    return;
  }
  if (y + p1.second < 0 || paper[x + p1.first][y + p1.second] != '9')
  {
    backtracking(idx, paper, x, y + 1, count);
    return;
  }
  bool isWrong = false;
  int i = 0;
  for (; i < st[number].size(); i++)
  {
    auto p = st[number][i];
    int insertX = x + p.first;
    int insertY = y + p.second;
    if (insertX < 0 || insertY < 0 || insertX >= paper.size() || insertY >= paper.size() || paper[insertX][insertY] != '9')
    {
      isWrong = true;
      break;
    }
    paper[insertX][insertY] = numberC;
    if (startPoint.first == insertX && startPoint.second == insertY)
    {
      startPoint.second++;
    }
    if (startPoint.second >= paper.size())
    {
      startPoint.first++;
      startPoint.second = 0;
    }
    count--;
  }
  if (!isWrong)
  {
    bool needChange = false;
    for (int i = 0; i < paper.size(); i++)
    {
      int cmpV = answer[i].compare(paper[i]);
      bool breaked = false;
      for (int j = 0; j < paper.size(); j++)
      {
        if (paper[i][j] == '9')
        {
          needChange = true;
          breaked = true;
          break;
        }
      }
      if (breaked)
      {
        break;
      }
      if (cmpV > 0)
      {
        needChange = true;
        break;
      }
      if (cmpV < 0)
      {
        break;
      }
    }
    if (idx + 1 > 5 && count == 0)
    {
      findAnswer = true;
      if (needChange)
      {
        for (int i = 0; i < paper.size(); i++)
        {
          for (int j = 0; j < paper.size(); j++)
          {
            answer[i][j] = paper[i][j];
          }
        }
      }
    }
    if (needChange && idx + 1 <= 5)
    {
      backtracking(idx + 1, paper, startPoint.first, startPoint.second, count);
    }
  }
  i--;
  for (; i >= 0; i--)
  {
    auto p = st[number][i];
    paper[x + p.first][y + p.second] = '9';
    startPoint = min(startPoint, {x + p.first, y + p.second});
    count++;
  }
  backtracking(idx, paper, x, y + 1, count);
}

int main()
{
  // freopen("../input.txt", "r", stdin);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int size;
  cin >> size;
  string initString = "";
  for (int i = 0; i < size; i++)
  {
    initString += "9";
  }

  vector<string> paper(size, initString);
  int count = size * size;
  answer.resize(size, initString);
  for (int cnt = 1; cnt <= 5; cnt++)
  {
    int x, y;
    cin >> x >> y;
    char c;
    bool findFirst = false;
    int firstX;
    int firstY;
    pieceSize[cnt].second = cnt + '0';
    for (int i = 0; i < x; i++)
    {
      for (int j = 0; j < y; j++)
      {
        cin >> c;
        if (c == '#')
        {
          pieceSize[cnt].first--;
          if (!findFirst)
          {
            findFirst = true;
            firstX = i;
            firstY = j;
          }
          st[cnt].push_back({i - firstX, j - firstY});
        }
      }
    }
  }
  sort(pieceSize.begin() + 1, pieceSize.end());
  backtracking(1, paper, 0, 0, count);
  if (findAnswer)
  {
    for (int i = 0; i < size; i++)
    {
      cout << answer[i] << '\n';
    }
  }
  else
  {
    cout << "gg\n";
  }
  // cout << callCnt;
  return 0;
}

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

문제

문제

출처

ICPC

왜 시간초과가 나는지 모르겠네요.

pch6789 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말