글 읽기 - 맞았는데 의문이 하나 있습니다.

kyoungin 5년 전 0

궁수3명의 위치를 순열로 돌려가면서 조건에 맞는 결과를 내도록 짰는데,

초기의 적의 수가 몇명인지 계산하는 것을

순열을 돌기전에 받으면 시간초과가 나고, (코드 61)

순열을 도는 반복문 안에 넣으면 통과되네요,, (코드 68)

이해가 잘안갑니다

도와주세요 ㅠㅠ

그러면 순열 돌릴때마다 같은 값을 계속 계산하는 건데 이게 더 비효율적인거 아닌가요,,?

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <math.h>
#include <set>
using namespace std;
#define p pair<int,int>
set<p> s;
set<p>::iterator iter;
int n,m,d;
vector<vector<int>> remap(vector<vector<int>> map){//궁수 한칸 아래로
    for(int i=0;i<m;i++){
        for(int j=n-1;j>=0;j--){ //y
            if(j==0){
                map[j][i]=0;
                continue;
            }
            map[j][i]=map[j-1][i];
        }
    }
    return map;
}

void solve(int x,vector<p> enemy){//죽일 수 있는 적 찾기
    vector<p> e_pos; //p (x,y)
    int e_d=1000000;
    for(int i=0;i<enemy.size();i++){
        int temp_d=abs(n-enemy[i].first)+abs(x-enemy[i].second);
        if(temp_d>d) continue;
        if(temp_d < e_d) {
            e_d =temp_d;
            e_pos.clear();
            e_pos.push_back(p(enemy[i].second,enemy[i].first));
        }
        else  if(temp_d == e_d) {
            e_pos.push_back(p(enemy[i].second,enemy[i].first));
        }
    }
    
    if(e_pos.size()!=0){
        sort(e_pos.begin(),e_pos.end());
        s.insert(p(e_pos[0].second,e_pos[0].first));
    }
        return ;
}
int main(){
    int i,j,res=-1,cnt,die=0,len=0;
    cin >> n >> m >>d;
    vector<vector<int>> inter(n+1),map;
    vector<p> enemy;
    for(i=0;i<n+1;i++){
        inter[i].resize(m);
        if(i==n){ //궁수 배치
            for(j=0;j<3;j++)
                inter[i][j]=1;
            continue;
        }
        for(j=0;j<m;j++){
            cin >> inter[i][j];
            //if(inter[i][j]==1)
              //      len++;
        }
    }
    do{
        map=inter;
        die=0,len=0,cnt=0;
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                if(map[i][j]==1)
                    len++;
            }
        }
        while(1){
            s.clear();
            enemy.clear();
            for(i=0;i<n;i++){
                for(j=0;j<m;j++){
                    if(map[i][j]==1)
                        enemy.push_back(p(i,j));
                }
            }
            
            for(i=0;i<m;i++){
                if(map[n][i]==1){
                    solve(i,enemy);
                }
            }
            
            for(iter=s.begin();iter!=s.end();iter++){
                int del_y =(*iter).first;
                int del_x =(*iter).second;
                for(j=0;j<enemy.size();j++){
                    if(enemy[j].first==del_y && enemy[j].second==del_x){
                        map[del_y][del_x]=0;
                        cnt++;
                        break;
                    }
                }
            }
            for(i=0;i<m;i++){
                if(map[n-1][i]==1)
                    die++;
            }

            if(len==die+cnt)
                break;
            map =remap(map);
            
        } //while(1)
        if(cnt>res) res=cnt;
    }while(prev_permutation(inter[n].begin(),inter[n].end()));
    
    cout <<res<<endl;
}

ha_ram 5년 전 1

시간초과 나는 코드가 어떤지는 잘 모르겠지만

여기 쓰신대로 68번째 줄부터 73번째 줄까지 지우고

61, 62번째 주석처리한것을 살린것만 보면은

67번째 줄에 len=0으로 바꾸는 것때문에 시간초과가 날겁니다.

kyoungin 5년 전 0

@ha_ram

앗 ! 코드 최적화하다가 저 부분을 간과하고 있었네요 ㅠㅠ!!

감사합니다 !!!!!!!!

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

문제

문제

출처

ICPC

맞았는데 의문이 하나 있습니다.

kyoungin 5년 전 0

ha_ram 5년 전 1

kyoungin 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말