글 읽기 - 시간 초과를 해결하는 방법이 궁금합니다.

luck3862 7년 전 0

코드는 아래와 같은데 시간초과가...흠흠 어떤식으로 코딩을하면 시간초과가 안날까염??

#include <iostream>
#include <string>
using namespace std;
int main(){
    int totalNum;
    cin>>totalNum;
    int totalCs[totalNum];
    string checkIt[totalNum*2];
    for(int i=0;i<totalNum;i++){
        cin>>totalCs[i];
        cin>>checkIt[i*2];
        cin>>checkIt[i*2+1];
    }
    for(int i=0;i<totalNum;i++){
      int cntEX=0;
        for(int j=0;j<totalCs[i];j++){
          char tmp;
          if(checkIt[i*2][j]!=checkIt[i*2+1][j]){
            int trash=1;
            for(int k=j+1;k<totalCs[i];k++){
              if(checkIt[i*2][k]!=checkIt[i*2+1][k]&&checkIt[i*2][k]!=checkIt[i*2][j]){
                trash=0;
                cntEX++;
                tmp=checkIt[i*2][j];
                checkIt[i*2][j]=checkIt[i*2][k];
                checkIt[i*2][k]=tmp;
                break;
              }
            }
            if(trash){
              cntEX++;
              checkIt[i*2][j]=checkIt[i*2+1][j];
            }
          }
        }
        cout<<cntEX<<endl;
    }
}

exqt 7년 전 2

맞지 않는 쌍을 찾아서 서로 바꾸어 주시는거 같은데 이렇게 되면 시간이 N^2에 비례하게 됩니다.

이를 해결하기 위해서 다음의 아이디어가 필요합니다.

1. B/B, W/W 이면 바꿀 필요가 없습니다. 생각해야 할 경우는 B/W, W/B 두가지 입니다.

2. B/W, W/B가 있는 "위치"는 그닥 중요하지 않습니다. B/W, W/B 의 "개수"만 생각해봅시다.

3. 2가지 작업중에 첫번째 작업을 수행하는것이 이득입니다.

luck3862 7년 전 0

답변 감사합니다~~~

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

문제

문제

출처

ICPC

시간 초과를 해결하는 방법이 궁금합니다.

luck3862 7년 전 0

exqt 7년 전 2

luck3862 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말