개발자 김수진

처음에 아래와 같이 풀었는데 메모리 초과 발생.

아무래도 2차원 배열에 의해서 메모리 초과가 발생한 것 같다.

int형 약 4억 개면 1.6GB 정도 되는데 문제 조건에서는 메모리가 256MB로 제한되어 있다.

#include <iostream>
#include <queue>

using namespace std;

int N,M;
int map[20002][20002]={0,};
int dis[20002]={0,};

int main(void)
{
    queue <int> q;
    int start,end;

    cin >> N >> M;
    for(int i=0;i<M;i++){
        cin >> start >> end;
        map[start][end]=1;
    }
    
    q.push(1);
    dis[1] = 0;
    
    while(!q.empty()){
        start = q.front();
        q.pop();
        
        for(int i=2;i<N+1;i++){
            
            if(dis[i]!= 0) continue;
            if(map[start][i]){
                dis[i] = dis[start]+1;
                q.push(i);
            }
        }
    }
    
    int MAX=0;
    int idx =0;
    int cnt =0;
    
    for(int i=1;i<N+1;i++){
        if(MAX < dis[i]){
            cnt =0;
            MAX = dis[i];
            idx = i;
        }
        if(MAX == dis[i])    cnt++;
    }
    
    cout << idx << " " << dis[idx] << " " << cnt;
    
    return 0;
}

따라서 크기가 고정된 배열 대신 메모리를 동적으로 할당하는 벡터를 사용하였다.

2차원 배열 대신 벡터를 사용하니 메모리 초과가 발생하지 않았다.

#include <iostream>
#include <queue>

using namespace std;

int N,M;
vector <int> map[20001];
int dis[20002]={0,};

int main(void)
{
    queue <int> q;
    int start,end;

    cin >> N >> M;
    for(int i=0;i<M;i++){
        cin >> start >> end;
        map[start].push_back(end);
        map[end].push_back(start);
        
    }
    
    q.push(1);
    dis[1] = 0;
    
    while(!q.empty()){
        start = q.front();
        q.pop();
        
        for(int j=0 ; j<map[start].size();j++){
            if(dis[map[start][j]]!= 0 || map[start][j]== 1) continue;
            dis[map[start][j]] = dis[start]+1;
            q.push(map[start][j]);
            
        }
    }
    
    int MAX=0;
    int idx =0;
    int cnt =0;
    
    for(int i=1;i<N+1;i++){
        if(MAX < dis[i]){
            cnt =0;
            MAX = dis[i];
            idx = i;
        }
        if(MAX == dis[i])    cnt++;
    }
    
    cout << idx << " " << dis[idx] << " " << cnt;
    
    return 0;
}

처음에 아래와 같이 정말 단순하게 풀었더니 시간초과가 나왔다.

생각해보니 input의 개수가 1,000,000 개가 되면 시간이 O(NM)이 되어 시간 초과가 나올 것이다.

#include <iostream>
#include <vector>

using namespace std;

// N : 나무의 수 , M : 집으로 가져가려는 나무의 길이

int N,M;
int tree[1000000]={0,};
int MAX=0;

int main(void)
{
    vector <int> tree;
    
    cin >> N >> M;
    
    for(int i=0;i<N;i++){
        int len;
        
        cin >> len;
        tree.push_back(len);
        if(MAX < tree[i])   MAX = tree[i];
    }
    

    while(MAX >= 0){
        int height=0;
        MAX--;
        
        for(int i=0;i<N;i++){
            if(tree[i] > MAX)   height += tree[i] - MAX;
        }
        
        if(height >= M)  break;
    }
    cout << MAX;
    return 0;
    
}

그래서 알고리즘을 찾아봤다. 이분탐색

#include <iostream>
#include <vector>

using namespace std;
//Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치
//번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

int N;
int visited[20];
int ability[20][20];
int MIN = 999999999;


void solve()
{
    int s=0;
    int l=0;
    
    for(int i=0;i<N;i++){
        if(visited[i]){
            for(int j=0;j<N;j++){
                if(visited[j])  s += ability[i][j];
            }
        }
        
        else if(!visited[i]){
            for(int j=0;j<N;j++){
                if(!visited[j]) l += ability[i][j];
            }
        }
    }

    int res = s > l ? s-l : l-s;
    if(res < MIN)   MIN =res;
    
}
        
void DFS(int cnt,int idx)
{
    if(cnt == N/2)
    {
        solve();
        return;
    }
    
    for(int i=idx;i<N;i++){
        
            visited[i]=1;
            DFS(cnt+1,i+1);
            visited[i]=0;
        
    }
}

int main(void)
{
    cin >> N ;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)
            cin >>ability[i][j];
    }

    DFS(0,0);
    cout << MIN;
    
    return 0;
}

처음에 solve에서 스타트와 링크 벡터 각각 선언해줘서 

벡터에 insert하고 2중 for 문 각각 2개씩 돌려서 시간초과가 발생한 줄 알았다.

그래서 solve 함수를 visited 배열을 사용해서 2중 for문 하나로 바꿔줘서 제출했는데 또 시간초과

그래서 DFS 부분을 바꿔줬다. 

원래  idx가 없었는데 idx를 추가해줘서 visited가 1인지 확인하는 조건문 없애주고

for문을 idx부터 시작해서 돌리니까 드디어 맞았습니다.

중복 가능, 오름차순

맨 처음에 아무 생각 없이 풀었다가

1 3 1

1 2 1

이런 것들도 가능하게 해서 틀렸다 

DFS 함수에서 재귀할 때 idx 인자를  i로 바꿔주니 맞았다.

#include <iostream>
#include <vector>

using namespace std;

vector <int> v;

int N,M;

void DFS(int cnt, int idx)
{
    if(cnt == M ){
        for(int i=0;i<M;i++)
            cout << v[i] <<" ";
        cout << "\n";
        return ;
    }
    
    for(int i=idx;i<N;i++){
        v.push_back(i+1);
        DFS(cnt+1,i);
        v.pop_back();
    }
}

int main(void)
{
    cin >> N >> M ;
    DFS(0,0);
    
    return 0;
}

DFS if문에서 return 안해줘서 처음에 답 이상하게 나왔다.

미친거 아닌가

어떻게 return을 빼먹지

#include <iostream>
#include <vector>


using namespace std;

int N,M;
vector <int> v;

void DFS(int cnt)
{
    if(cnt == M){
        for(int i=0;i<M;i++)
            cout << v[i] <<" ";
        cout << "\n";
        return;
    }
    
    for(int i=0;i<N;i++)
    {
        v.push_back(i+1);
        DFS(cnt+1);
        v.pop_back();
    }
}


int main()
{
    cin >> N >> M;
    DFS(0);
    
    return 0;
}

N과 M(1)에서 DFS의 매개변수로 index를 추가해주어 오름차순 조건을 맞춰줬다.

처음에 main에서 DFS 호출할 때 for문 사용해서 결과가 제대로 안나왔는데

진짜 DFS 이해를 아직 제대로 못한 것 같다. 

#include <iostream>

using namespace std;

int N,M;
int visited[8];


void DFS(int cnt, int idx)
{
    if(cnt == M)
    {
        for(int i=0;i<N;i++){
            if(visited[i])
                cout << i+1 << " ";
        }
        cout << "\n";
        
    }
    
    for(int i=idx;i<N;i++){
        if(!visited[i]){
            visited[i]=1;
            DFS(cnt+1,i+1);
            visited[i]=0;
        }
    }
}

int main(void)
{
    cin >> N >> M ;

    DFS(0,0);
    return 0;
    
}

보자마자 DFS 기본 문제 같았다

근데 당연히 맞을 줄 알았는데 시간초과 나와서 당황했다

알고보니 endl 대신 '\n' 이거 하나  바꿔주니 바로 맞았다.

endl이 시간 많이 잡아먹는듯 하다.

앞으로는 절대 안써야지

#include <iostream>
#include <vector>

using namespace std;

int N,M;
int visited[8];

vector <int> v;

void DFS (int cnt)
{
    if(cnt == M)
    {
        for(int i=0;i<M ;i++)
        {
            cout <<v[i] << " ";
        }
        cout << "\n";
    }
        
    for(int i=0;i<N;i++){
        if(!visited[i]){
            visited[i]=1;
            v.push_back(i+1);
            DFS(cnt+1);
            visited[i]=0;
            v.pop_back();
        }
    }
}

int main()
{
    cin >> N >>M;
    DFS(0);
    return 0;
    
}

#include <iostream>

using namespace std;

//1인 경우는 시계 방향이고, -1인 경우는 반시계 방향
// N극은 0, S극은 1로 나타나있다.

int K; //회전 횟수
int wheel[4][8];
int tmp[4][8];


void rotate(int idx, int dir)
{
    if(dir ==1 ){
        for(int i=0;i<7;i++)
            wheel[idx][i+1] = tmp[idx][i];
        wheel[idx][0] = tmp[idx][7];
    }
    
    else{
        for(int i=1;i<8;i++)
            wheel[idx][i-1] = tmp[idx][i];
        wheel[idx][7] = tmp[idx][0];
    }
}


int check(int idx)
{
    if(idx == 1){
        if(tmp[0][2] == tmp [1][6]) return 0;
        else return 1;
    }
    else if(idx == 2){
        if(tmp[1][2] == tmp[2][6])  return 0;
        else return 1;
    }
    else if (idx ==3){
        if(tmp[2][2] == tmp[3][6])  return 0;
        else return 1;
    }
    
    return 0;
    
}

int main(void)
{
    
    for(int i=0;i<4;i++){
        for(int j=0;j<8;j++)
            scanf("%1d",&wheel[i][j]);
    }
    
    cin >> K;
    
    for(int i=0;i<K;i++){
        
        for(int i=0;i<4;i++){
            for(int j=0;j<8;j++)
                tmp[i][j]=wheel[i][j];
        }
        int idx,dir;
        cin >> idx >> dir;
        idx--;
        
        rotate(idx,dir);
        
        switch(idx)
        {
            case 0:
                while(1){
                    idx++;
                    if(idx == 4)    break;
                    
                    if(dir == 1)    dir =0;
                    else    dir =1;
                    
                    if(check(idx))  rotate(idx,dir);
                    else    break;
                }
                break;
                
            case 1:
                if(check(1)){
                    if(dir == 1)    rotate(0,0);
                    else    rotate(0,1);
                }
                
                while(1){
                    idx++;
                    if(idx == 4)    break;
                    
                    if(dir == 1)    dir =0;
                    else    dir =1;
                    
                    if(check(idx))  rotate(idx,dir);
                    else    break;
                }
                break;
                
            case 2:
                if(check(3)){
                    if(dir == 1)    rotate(3,0);
                    else    rotate(3,1);
                }
                
                while(1){
                    idx--;
                    if(idx == -1)    break;
                    
                    if(dir == 1)    dir =0;
                    else    dir =1;
                    
                    if(check(idx+1))  rotate(idx,dir);
                    else    break;
                }
                break;
                
            case 3:
                while(1){
                    idx--;
                    if(idx == -1)    break;
                    
                    if(dir == 1)    dir =0;
                    else    dir =1;
                    
                    if(check(idx+1))  rotate(idx,dir);
                    else    break;
                }
                break;
        }
    }
    //1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점

    int total=0;
    
    if(wheel[0][0]) total+=1;
    if(wheel[1][0]) total+=2;
    if(wheel[2][0]) total+=4;
    if(wheel[3][0]) total+=8;

    cout << total << "\n";
    
    return 0;
}

한번 풀었던 문제인데 예전에는 '틀렸습니다!'가 나왔지만 이번에는 맞았다.

이렇게 조건 하나씩 따져가면서 직접 다 구현하는 문제를 시뮬레이션이라고 하는 것 같다.

아직 시뮬레이션이 제일 막막하다.

다른 알고리즘들은 방법에 맞게 풀면 될텐데 이거는 하나씩 다 따지는 방법밖에 없으니 조건 잘 따져가면서 풀어야 할듯!

그리고 처음에 input 값 제대로 안따져줘서 틀렸다.