개발자 김수진

[문제]

https://www.acmicpc.net/problem/14890

시뮬레이션 문제로 

높이가 같은 경우 -> 다음 index로 넘어감

높이가 다른 경우 -> 차이가 1보다 큰지 확인 

행과 열을 올렸다 하나의 일차원 배열에 옮겨서 확인 

(어차피 행과 열 확인하는 방법은 같으니까)

[풀이]

1. check 함수

다음 인덱스랑 높이 비교  

높이차가 같은 경우 다음 인덱스로 넘어감. 

높이차가 1보다 크다면 check 함수 바로 return.

높이차가 1인 경우 comp 함수 호출.

0부터 N-1까지 확인 

N-1까지 도달한 경우 cnt (지나갈 수 있는 길의 갯수 ) 1 증가 

2. comp 함수

경사로를 추가할 수 있는지 확인

추가할 부분의 길이가 경사로의 길이보다 짧으면 안된다.

조심해야될 부분은 위의 [그림 1]과 같이 경우에는 경사로를 무조건 2개 추가하는 경우부터 가능하다. 

(코드 25번째 line에서 처리 ) 

또 [그림 2]의 경우 return tmp+1을 해줬는데 

4 4 3 3 3 2 2 , 경사로 : 3 

위의 경우 통과하지 못하는 케이스인데 tmp+1 (arr[5])부터 체크하므로 통과하게 된다.

=> 따라서 return tmp로 바꿔서 arr[4]부터 체크하도록 해줬다. (코드 24번째 line) 

(이 부분 놓쳐서 계속 틀렸다.) 

[코드]

시간 : 0ms

#include <iostream>
#define MAX 100

using namespace std;

int N,L;
int map[MAX][MAX]={0,};
int cnt =0;

int comp(int pos , int arr[100])
{
    int tmp;
    
    if ( arr[pos] > arr[pos+1]){
        tmp = pos+1;
        int len=1;
        while(tmp < N-1){
            if(arr[tmp] != arr[tmp+1])  break;
            len++;
            tmp++;
        }
        if(len < L )    return 0;
        else if(tmp == N-1)  return N-1;
        else if((arr[pos]-arr[tmp+1])== 2)   return tmp;
        else if((len/L) >= 2 &&  (arr[pos] == arr[tmp+1]))  return tmp+1;
        else  return 0;
    }
    else {
        tmp = pos;
        int len =1;
        while(tmp > 0){
            if(arr[tmp] != arr[tmp-1])  break;
            len++;
            tmp--;
        }
        if(len < L )    return 0;
        else    return pos+1;
    }
}

void check(int idx,bool flag)
{
    
    int arr[N];
    
    if(flag)    for(int i=0;i<N;i++)    arr[i] = map[i][idx];
    else    for(int i=0;i<N;i++)    arr[i] = map[idx][i];
    
    int pos =0;
    
    while(pos < N-1 ){
        
        int diff = arr[pos] - arr[pos+1];
        
        if( diff == 0)  pos++;
        else if(diff==1 || diff == -1){
            pos = comp(pos , arr);
            if(pos ==0) return ;
        }
        else    return ;
    }
    
    cnt++;
}

int main(void)
{
    cin >> N >> L;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)    cin >> map[i][j];
    }
    
    for(int i=0;i<N;i++){
        check(i,0); // row
        check(i,1); // col
    }
    
    cout << cnt;
    
    return 0;
}

조언, 질문 환영입니다!

댓글 남겨주세요~

[ 정의 ]

프로세서가 자원을 얻지 못해 무한정 기다리며 다음 처리를 하지 못하는 상태 

특정 자원에 대해 여러 프로세스가 경쟁 상태일 때 발생한다.

'데드락' 또는 '교착상태'라고 한다 .

아래 [그림 1]과 같이 P1 프로세스가 R1을 점유, P2 프로세스가 R2를 점유하고 있는 상태에서

P1은 R2 리소스에 접근 요청을 보내고 , P2는 R1 리소스에 접근 요청을 보낸다면

두 프로세스는 리소스를 할당받지 못하고 계속 대기상태이다.

이러한 상태를 데드락(DeadLock) 이라고 한다. 

[ 데드락 발생 조건  ]

아래 4가지 조건을 모두 만족시키면 데드락 발생.

( 4가지 조건 모두 만족시킨다고 무조건 데드락 발생하는건 아니다.)

데드락이 발생할 경우 4가지 조건을 모두 만족한다. 

• Mutual Exclusion
• Hold and Wait
• No Preemption
• Circular Wait

1. Mutual Exclusion ( 상호 배제 )

 한번에 한 프로세스만 자원을 사용할 수 있다.

2. Hold and Wait ( 점유와 대기 )

 하나의 프로세스가 자원을 점유하고 있으면서 다른 자원을 할당 받기를 원한다. 

3. No Preemption ( 비선점 )

점유해제는 해당 리소스를 점유하는 프로세스에 의해서만 점유해제가 가능하다. 

( 다른 프로세스가 점유하는 자원을 뺏어올 수 없다. )

4. Circular Wait ( 환형 대기 ) 

프로세스와 자원들이 원형을 이룬다.

각 프로세스는 자원을 점유하면서 상대방 프로세스가 점유한 자원을 상호 요청

{ P0, P1, P2, ... ,PN } 프로세스가 존재

- P0 프로세스는 P1 프로세스가 점유한 자원을 대기 

- P1 프로세스는 P2 프로세스가 점유한 자원을 대기 

.

.

- PN 프로세스는 P0 프로세스가 점유한 자원을 대기 

이와 같이 서로 맞물리는 형태로 프로세스가 자원을 요청하며 대기

[ 데드락 예방 조건  ]

위의 발생 조건이 하나라도 만족하지 않는다면 데드락을 예방할 수 있다.

1. Mutual Exclusion ( 상호 배제 ) 부정

하나의 자원에 대해 여러 프로세스가 자원을 공유할 수 있도록 한다 .

2. Hold and Wait ( 점유와 대기 ) 부정 

프로세스가 실행되기 전 , 필요한 모든 자원을 할당받는다.

3. No Preemption ( 비선점 ) 부정 

자원을 점유하고 있는 프로세스가 다른 자원을 요청할 경우,

점유하고 있는 자원을 반납하고 요청한 자원을 기다리도록 한다.

4. Circular Wait ( 환형 대기 ) 부정 

자원에 고유한 번호를 할당하고 , 번호 순서대로 자원을 요구하도록 한다, 

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo&categoryId=AWXRUN9KfZ8DFAUo&categoryType=CODE

[풀이]

시뮬레이션 문제인 것 같다.

문제 조건만 잘 따져주면서 풀면 된다. 

N개의 숫자를 입력 받아서 사각형 각 변에 존재하는 숫자 조합 중에서 K번째로 큰 수를 구하면 된다.

(숫자 조합이 중복되는 것이 없도록 주의)

1. 회전하기

사각형에 존재하는 각 숫자들은 시계방향으로 한칸씩 이동한다. 

=> 총 N/4 번 회전하면 처음 상태로 돌아온다. 

2. 각 변에 있는 문자들의 합 구하기 

16진수이므로 N/4번째 자리수부터 16씩 곱해주어 더하여 전체 합을 구한다.

3. 최댓값 구하기 

2번에서 구한 값을 벡터에 넣어준다. ( 중복 없이 )

벡터에 다 넣어준 뒤  sort 함수를 사용해 K번째로 작은 수 출력.

[코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,K;
char map[4][8]={0,};
vector <int> num;

bool comp(int a, int b)
{
    return a>b;
}
void calc()
{
    int idx = N/4-1; // 2~8

    for(int i=0;i<4;i++){
     
        int sum=0;
        int tmp = 1;
        
        
        for(int j=idx;j>=0;j--){
            
            if(48<=map[i][j] && map[i][j] <=57){ //아스키코드 0~9
                sum += tmp * (map[i][j]-48);
            }
            else    sum += tmp * (map[i][j] - 55); // 아스키코드 A~F
            
            tmp *=16;
            
        }
        
        if(find(num.begin(),num.end(), sum) == num.end())   num.push_back(sum);
    }
}
void rotate()
{
    int idx = N/4-1; // 2~8
    char tmp[4]={0,};
    
    for(int i=0;i<4;i++)    tmp[i] = map[i][idx];
    
    while(idx>0){
        
        for(int i=0;i<4;i++){
            map[i][idx] = map[i][idx-1];
        }
        idx--;
    }
    
    for(int i=0;i<3;i++)    map[i+1][0] = tmp[i];
    map[0][0] = tmp[3];
    
}

void init()
{
    for(int i=0;i<4;i++){
        for(int j=0;j<8;j++)    map[i][j] = {0,};
    }
    num.clear();
    
}

int main(void)
{
    
    int T;
    cin >> T;
    
    for(int k=0;k<T;k++){
        init();
        
        cin >> N >> K;
        for(int i=0;i<4;i++){
            for(int j=0;j<N/4;j++){
                cin >> map[i][j];
            }
        }
        
        for(int i=0;i<N/4;i++){
            rotate();
            calc();
        }
        
        sort(num.begin(), num.end(),comp);
        cout << "#" << k+1 << " " << num[K-1]<<"\n";
    }
    return 0;
}

조언, 질문 환영입니다!

댓글 남겨주세요~

벡터 시간 오래 걸릴까봐 안 쓰고 풀었는데

오히려 벡터 사용하니까 더 빠르다.

DFS로 접근 

- 벡터 대신 반복문 사용

시간  :  124ms

#include <iostream>
#define MAX 20

using namespace std;

int N;
int map [MAX][MAX]={0,};
int visited[20]={0,};
int MIN = 1e9;


void solve()
{
    int start=0;
    int link=0;
    
    for(int i=0;i<N;i++)
    {
        if(visited[i]==1){
            for(int j=0;j<N;j++)    if(visited[j]==1)   start+=map[i][j];
        }
        else{
            for(int j=0;j<N;j++)    if(visited[j]==0)   link+=map[i][j];
        }
    }
    
    int res = start > link ? start-link : link - start;
    if( MIN > res)  MIN = res;
    
}

void DFS(int cnt,int idx)
{
    if(cnt == N/2)
    {
        solve();
        return;
    }
    
    for(int i=idx;i<N;i++){
        if(visited[i]==0)
        {
            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++)
            scanf("%d",&map[i][j]);
    }
    
    DFS(0,0);
    cout << MIN;
    return 0;
}

- 벡터 사용 

시간 : 100ms

#include <iostream>
#include <vector>

#define MAX 20

using namespace std;

int N;
int map [MAX][MAX]={0,};
int visited[20]={0,};
int MIN = 1e9;


void solve()
{
    int start=0;
    int link=0;
    
    vector <int> s;
    vector <int> l;

    for(int i=0;i<N;i++)
    {
        if(visited[i])  s.push_back(i);
        else    l.push_back(i);
    }
    
    for(int i=0;i<N/2;i++)
    {
        for(int j=0;j<N/2;j++){
            start += map[s[i]][s[j]];
            link += map[l[i]][l[j]];
        }
    }
    
    int res = start > link ? start-link : link - start;
    if( MIN > res)  MIN = res;
    
}

void DFS(int cnt,int idx)
{
    if(cnt == N/2)
    {
        solve();
        return;
    }
    
    for(int i=idx;i<N;i++){
        if(visited[i]==0)
        {
            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++)
            scanf("%d",&map[i][j]);
    }
    
    DFS(0,0);
    cout << MIN;
    return 0;
}

다른분들 풀이 보니까 DFS 사용 안하고 0ms로도 풀던데 한번 참고해봐야겠다.

조언, 질문 환영입니다!

댓글 남겨주세요~

[풀이 1]

처음에 시뮬레이션인줄 알고 조건 하나씩 다 따지면서 아래와 같이 구현

#include <iostream>

using namespace std;

//0: 빈칸, 1:벽

int N,M;
int map[50][50];
int dir;
int x,y;
int cnt=0; // number of clean space by robot

//0:북 , 1:동, 2:남, 3:서
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int main(void)
{
    
    cin >> N >> M ;
    cin >> x >> y >> dir;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cin >> map[i][j];
    }
    
    while(1){
        
        if(map[x][y]==0){
            map[x][y]=2; //현재 위치 청소
            cnt++;
        }
        
        int pdir = dir;
        
        for(int i=0;i<4;i++){
            //왼쪽으로 회전
            if(dir == 0)    dir = 3;
            else    dir-=1;
            
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            if(map[nx][ny]==0){ //왼쪽으로 회전했을 때, 청소할 공간이 존재하는 경우
                x = nx; y= ny;
                break;
            }
        }
        
        if(pdir == dir && map[x][y] != 0 ) //후진하는 경우
        {
            x =x-dx[dir];
            y =y-dy[dir];
        }
        
        if(map[x][y] == 1)  break; // 후진했는데 벽인 경우
        
            }
    
    cout << cnt;
    return 0;
    
}

[풀이 2]

맞았습니다가 나왔지만 구글링을 해보니 DFS를 사용하여 재귀함수로 풀 수 있다는 것을 아래와 같이 재귀함수를 사용해서 풀어봤다.

#include <iostream>

using namespace std;

//0: 빈칸, 1:벽

int N,M;
int map[50][50];
int cnt=0; // number of clean space by robot

//0:북 , 1:동, 2:남, 3:서
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};


void DFS(int x , int y, int dir){
    
    map[x][y]=2;

    for(int i=0;i<4;i++){
        
        if(dir == 0)    dir = 3;
        else    dir-=1;
        
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        if(map[nx][ny]==0){
            DFS(nx,ny,dir);
            return;
        }
    }
    /* 후진 하는 경우 */
    x-=dx[dir];
    y-=dy[dir];
    if(map[x][y]==1)    return;
    else    DFS(x,y,dir);

}
int main(void)
{
    int x,y,dir;
    
    cin >> N >> M ;
    cin >> x >> y >> dir;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cin >> map[i][j];
    }
    
    DFS(x,y,dir);
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            if(map[i][j]==2)    cnt++;
    }
    cout << cnt;
    return 0;
    
}

재귀함수를 사용하여 후진 부분에서 시뮬레이션보다 훨씬 간단하게 풀 수 있었다.

조언, 질문 환영입니다!

댓글 남겨주세요~

#include <iostream>

using namespace std;

int N,M,K;
int map[20][20]={0,};
int x,y;

int dx[4] ={0,0,-1,1};
int dy[4] = {1,-1,0,0};
int dice[7]={0,};

//지도 위 : 1 , 동쪽 : 3 ,
// 처음 주사위 모든 면에 0
// 이동한 칸이 0인 경우 -> 주사위에 있는 숫자가 바닥면으로
// 0이 아닌 경우 -> 주사위로 복사되고 칸은 0으로
int main(void)
{
    cin >> N >> M >> x >> y >> K;
        
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cin >> map[i][j];
    }
    
    for(int i=0;i<K;i++){
        
        int dir;
        cin >> dir;
        
        int nx = x + dx[dir-1];
        int ny = y + dy[dir-1];
        
        if( nx < 0 || ny <0 || nx >= N || ny >= M)  continue;
        
        int top = dice[1];
        
        if ( dir == 1 ){
            dice[1] =dice[4];
            dice[4] =dice[6];
            dice[6] =dice[3];
            dice[3] =top;
        }
        else if ( dir == 2 ){
            dice[1] =dice[3];
            dice[3] =dice[6];
            dice[6] =dice[4];
            dice[4] =top;
        }
        else if(dir ==3 ){
            dice[1] =dice[5];
            dice[5] =dice[6];
            dice[6] =dice[2];
            dice[2] =top;
        }
        else if(dir ==4 ){
            dice[1] =dice[2];
            dice[2] =dice[6];
            dice[6] =dice[5];
            dice[5] =top;
        }
        
        cout << dice[1] << " ";

        if(map[nx][ny] ==0){
            map[nx][ny] = dice[6];
        }
        else{
            dice[6] = map[nx][ny];
            map[nx][ny] =0;
        }
       
        x = nx;
        y = ny;
    }
        
    return 0;
    
}

1. 이동한 좌표가 범위 내에 있는지 확인 

2. 방향에 알맞게 주사위 움직이기

3. 해당 좌표에 map 값이 0이면 주사위 값을 map에 복사.

0이 아니라면 map 값을 주사위에 복사하고, map을 0으로 초기화

4. 좌표 update

top 부분은  dice[1]로 고정하고 방향에 따라 움직인 뒤 출력해주었다.

index가 헷갈릴까봐 주사위 배열 사이즈를 7로 할당하고 1~6의 index를 사용해서 풀었다.

삼성 기출문제에 비해 비교적 쉽게 풀 수 있는 문제였다.

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

아무래도 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;
    
}

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