잡다한 프로그래밍

https://swexpertacademy.com/main/main.do

1. 해결방법

많이 볼 수 있는 DFS 문제로 좌, 우, 아래 순으로 한 번만 체크하는 방식으로 해결하면 금방 풀 수 있을 거라 생각했다.

2. 에러

먼저 100X100 배열을 가로로 입력받아야 하는데 다음과 같은 코드로 세로를 먼저 받게 입력받았다. 이사실을 오랫동안 알아차리지 못해 문제에 오류가 생겼다. 주의하자 array[i][j]가 아닌 [j][i] 여야 한다

        for(int i = 0; i < 100; i++){
            for(int j = 0; j < 100; j++){
                cin >> array[i][j];
            }
        }

3. 코드

#include<iostream>

using namespace std;
int array[100][100] = {0};
int chk_array[100][100] = {0};
int result = 0;
int max_value = 9999;
int nx[3] = {-1, 1, 0};
int ny[3] = {0, 0, 1};

void dfs(int x, int y, int start, int count){
    if (y == 99){
        if(count <= max_value){
            max_value = count;
          	result = start;
        }
    }
    else{
        for(int i = 0; i < 3; i ++){
     		int dx = x + nx[i];
        	int dy = y + ny[i];

        	if(dx < 0 || dx >= 100 || dy < 0 || dy >= 100 || chk_array[dx][dy] == 1 || array[dx][dy] == 0 || (y == 0 && i == 0) || (y == 0 && i ==1)) continue;
			else{
                chk_array[dx][dy] = 1;
             	dfs(dx, dy, start, count+1);
                chk_array[dx][dy] = 0;
                break;
            }
    	}
        
    }    
}

int main(int argc, char** argv)
{
   int test_case;
   int T;   
   for(test_case = 1; test_case <= 10; ++test_case)
   {
      cin>>T;
        for(int i = 0; i < 100; i++){
            for(int j = 0; j < 100; j++){
                cin >> array[j][i];
            }
        }
        result = 0; max_value = 9999;
        for(int k = 0; k < 100; k++){
            chk_array[k][0] = 1;
            dfs(k, 0, k, 1);
            chk_array[k][0] = 0;
        }
        cout << "#" << test_case << " " << result << endl;

   }
   return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

https://swexpertacademy.com/main/main.do

1. 해결방법

벡터를 사용하여 방향 그래프를 저장하였고, 이를 DFS완전 탐색으로 해결하였다

2. 에러 사항

vector를 초기화해주지 않아서 탐색 시간이 길어져 시간 초과가 생겼는데 clear() 함수가 제대로 작동하지 않아서 dfs함수에 vector를 넘겨주고 vector를 전역 변수가 아닌 메인 함수 내부에 선언하는 방식으로 해결하였다

3. 코드

#include<iostream>
#include<vector>
using namespace std;
int test_case;
int T;
int num;
int x, y;
int result = 0;

void vector_dfs(int now, vector<int>* vector){
    if(now == 99){
		result = 1;
        return;
    }else{
        for(int i = 0; i < vector[now].size(); i++){
                        vector_dfs(vector[now][i], vector);    
        }
    }
}

int main(int argc, char** argv)
{
	for(test_case = 1; test_case <= 10; ++test_case)
	{
		cin >> T;
        cin >> num;
		vector<int> vec[100];
        
        for(int i = 0; i < num; i++){
            cin >> x;
            cin >> y;
            vec[x].push_back(y);
        }
        result = 0;
        vector_dfs(0, vec);
            cout << "#" << test_case <<" " << result << endl;
    }
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

https://swexpertacademy.com/main/main.do

1. 해결방법

문제의 상하좌우라는 키워드를 보자마자 완전탐색이 가장 어울릴것이라는 생각이 들었다. DFS를 통해 순차적으로 탐색하면서 카운트 해주는 방법으로 해결하였다

2. 코드

#include<iostream>
using namespace std;

int test_case;
int T;
int N;
int ary[1000][1000];
bool ary_check[1000][1000];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int cnt_max = 1;
int val_min = 9999;
void check(int x, int y, int cnt, int start_value){
	ary_check[x][y] = true;
    
    for(int i = 0; i < 4; i++){
  		int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx < 0 || ny < 0 || nx >= N || ny >= N || abs(ary[nx][ny] - ary[x][y]) != 1 || ary_check[nx][ny]){
         
            
            continue;   
        }
        check(nx, ny, cnt+1, start_value);
      	ary_check[nx][ny] = false;
    }
   
    if(cnt_max < cnt){
             	cnt_max = cnt;
        val_min = start_value;
    }else if(cnt_max == cnt){
     	if(val_min > start_value)
            val_min = start_value;
    }
}

int main(int argc, char** argv)
{
	cin>>T;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
                        memset(ary, 0, sizeof(ary));
		for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                cin >> ary[i][j];
            }
        }
        
                        cnt_max = 1;
				val_min = 9999;
        for(int k = 0; k < N; k++){
            for(int n = 0; n < N; n++){

                check(k, n, 1, ary[k][n]);
                ary_check[k][n] = false;
            }
        }
        
		cout << "#" << test_case << " " << val_min << " " << cnt_max << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

https://swexpertacademy.com/main/main.do

1. 해결방법

1-1 오류발생

먼저 한 사람씩 비교하여 방문지로 체크했다가 다음 사람은 전에 방문했던적이 있는지 없는지 비교하여 cnt를 ++ 해주는 방법을 사용하였으나 첫방문자가 1~400까지 방문했을경우 나머지는 모두 ++ 되어버리는 오류가 존재하였다

1-2 오류코드

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

int N;
int now_room;
int next_room;
int cnt = 0;
int room[401] = {0};
int now_check;
int next_check;

int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin>>T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        memset(room, 0 , sizeof(room));
        cnt = 1;
        cin>>N;
        for(int i = 0; i < N; i++){
            cin >> now_room;
            cin >> next_room;
            if(now_room > next_room){
                swap(now_room, next_room);
            }
            
            for(int k = now_room; k<=next_room; k++){
                if(room[k]){
                     cnt++;
                    break;
                }
            }
            
                for(int j = now_room; j <= next_room; j++){
                    room[j] = 1;
                }
            
        }
        cout << "#" << test_case << " " << cnt << endl;
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

2. 해결

1번 방법과 비슷한대신 방문지를 ++해주고 마지막에 방문지중 가장 큰 값을 return한다 이방법으로 1번의 오류를 해결하였다

코드

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

int N;
int now_room;
int next_room;
int room[401] = {0};
int now_check;
int next_check;
int cnt = 0;
int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin>>T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		memset(room, 0 , sizeof(room));
        cin>>N;
        for(int i = 0; i < N; i++){
            cin >> now_room;
            cin >> next_room;
            if(now_room > next_room){
				swap(now_room, next_room);
            }

            if((now_room % 2) == 0) now_room--;
            if((next_room % 2) == 1) next_room++;
            
            for(int j = now_room; j <= next_room; j++){
             room[j]++;   
            }
        }
        cnt = *max_element(room, room+401);
        cout << "#" << test_case << " " << cnt << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

https://swexpertacademy.com/main/main.do

1. 해결방법

먼저 전에 가능한 시험 점수라는 문제를 풀면서 가능한 모든 점수를 구하는 문제를 푼 기억이 있어서 같은 방법으로 해결하면 좋겠다 라는 생각을 하였다. 가능한 시험 점수라는 방법으로 문제를 해결했으나, 깔끔한 코드가 아닌 것 같아서 다른 방법이 존재할까 찾아보았고 dfs로 가능하다는걸 알았다. 어렵지 않았는데 왜 dfs로 해결해볼까?라는 생각을 하지 못했다.

2. 코드

#include<iostream>
#include<string.h>
using namespace std;
	int test_case;
	int N;
	int top_height;
	int array[300000];
	int temp = 0;
	int sum = 0;
	int result = 0;
int main(int argc, char** argv)
{
    cin>>test_case;
	for(int i = 1; i <= test_case; i++)
	{
		cin >> N;
        cin >> top_height;
            memset(array, 0, sizeof(array));
        array[0] = 1;
       	for(int j = 0; j < N; j++){
            cin >> temp;
            sum += temp;
            for(int k = sum; k>=0; k--){
             if(array[k] != 0){
                 array[k + temp]++;
             }
            }
        
        }
        
         for(int m = 0; m< 300000; m++){
         if(array[m] !=0 && m >= top_height){
         	result = m - top_height;
                              break;
         }
        }

        
        cout << "#"<<i<<" "<< result << endl;
    }
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

https://swexpertacademy.com/main/main.do

1. 해결방법

먼저 100x100 배열을 세로로 돌며 위에서 아래로 돌 때는 2인 경우는 값을 0으로 1인 경우는 break 하는 포문을 반대로 아래서 위로 돌 때는 1인 경우는 값을 0으로 2인 경우는 break 하게 한다 이후 다시 정의된 배열의 개수를 세는 방식으로 코딩하였다

2. 코드

#include<iostream>
#include<string.h>

int array[100][100];
int sum = 0;
int test_case;
int T;

using namespace std;

void check(){
    for(int i = 0; i < T; i++){
            for(int j = 0; j < T; j++){
        		if(array[j][i] == 2){
                 array[j][i] = 0;   
                } else if(array[j][i] == 1){
                 break;   
                }
        	}
	}
    
    
        for(int i = T-1; i >= 0; i--){
            for(int j = T-1; j >= 0; j--){
        		if(array[j][i] == 1){
                 array[j][i] = 0;   
                } else if(array[j][i] == 2){
                 break;   
                }
        	}
	}
}

void count(){    
    sum = 0;
    for(int i = 0; i < T; i++){
        int check = 0;
    	for(int j = 0; j < T; j++){
            if(array[j][i] == 1){
                check = 1;
            }else if(array[j][i] ==2 && check == 1){
                    check = 0;
	                sum++;
            }
        }
	}
    
}

int main(int argc, char** argv)
{
    for(int test_case = 1; test_case <= 10; test_case++){
	cin>>T;
	
        memset(array, 0, 100);
        for(int i = 0; i < T; i++){
            for(int j = 0; j < T; j++){
        		cin >> array[i][j];
        	}
		}
        check();
        count();
        
        cout << "#"<<test_case<< " " << sum << endl;
        
	
    }
	return 0;
}

https://swexpertacademy.com/main/main.do

1. 해결방법

먼저 배열에 N개의 수를 입력받고 이를 정렬한 후, 늘어나는 시간과 비교하며 M시간이 되면 빵을 K개만큼 추가하고, 만약 배열의 값을 cnt로 두고 배열[cnt] == 시간일 경우 빵의 개수가 0보다 같거나 작으면 불가, 크면 빵의 개수를 줄이고 cnt를 1씩 늘리고 time도 1 늘리는 방법으로 해결하려 하였다

2. 오류

그러나 배열내부에 배열[0] == 3 배열[1] == 3같이 같은 값이 들어가 있을 경우 시간은 이미 늘어나버려서 무한루프에 빠지는 현상이 발생하였고 while문을 2번 돌리는 방법으로 다음과 같이 해결하였다. 더 쉬운 방법도 존재하는 것 같으니 다른 블로그도 참고하길 바란다.

3. 코드

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

string result = "Possible";
int tmp[101];
    int test_case;
	int T;
    int N;
    int M;
    int K;

void check(){
    int time = 0;
    int cnt = 0;
    int bread = 0;
	while(1){
        if(cnt == N) {break;}
        if((time % M) == 0 && time != 0) bread += K;
        
        while(1){
        if(tmp[cnt] == time){
         if(bread <=0){
             result = "Impossible";
             goto EXIT;
         }
         else{
          bread--;
          cnt++;
         }
      
        	}else{
         break;   
        }
        }
        
        time++;
    }

    EXIT:
    return;
}

int main(int argc, char** argv)
{
	scanf("%d",&T);
	for(test_case = 1; test_case <= T; ++test_case)
	{
        scanf("%d %d %d",&N ,&M ,&K);
		
        for(int i = 0; i < N; i++){
            scanf("%d", &tmp[i]);
        }
    
		sort(tmp, tmp+N);
        result = "Possible";
       check();
        
        printf("#%d %s\n", test_case ,result.c_str());
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

https://swexpertacademy.com/main/main.do

1. 해결방법

먼저 NXN Array를 지뢰 = -1 나머지 칸은 숫자로 바꾼 Change_Array를 만들고 바꾼 Change_Array의 값이 0이고, 방문 안 한 곳을 체크하게 하고, 문제 의도대로 8방향으로 dfs 하였다. 이후 값이 0과 -1 이아닌 값들 중 방문하지 않은 개수만큼 개수를 추가해주는 방법으로 해결하였다

2. 코드

코드는 다음과 같다

#include<iostream>
#include<string.h>
using namespace std;
	int T;
    int N;
char array[300][300];
int change_array[300][300];
bool chk_array[300][300];
int count = 0;
int dx[8] = {-1, 0, 1, -1, 1, -1, 0 ,1};
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

void change(){
     for(int i = 0; i < N; i++){         
        	for(int j = 0; j < N; j++){
				if(array[i][j] == '*') change_array[i][j] = -1;
                else{
                    int cnt = 0;
                    for(int k = 0; k < 8; k++){
                     	int nx = i + dx[k];
                     	int ny = j + dy[k];
                        if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                        if(array[nx][ny] == '*') cnt++;
                    }
                    change_array[i][j] = cnt;
                }
            }
        }
}

void dfs(int x, int y){
    chk_array[x][y] = true;
    
    for(int k = 0; k < 8; k++){
    	int nx = x + dx[k];
        int ny = y + dy[k];
        if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
        else{
         	if(change_array[nx][ny] == 0 && !chk_array[nx][ny]){
             	dfs(nx, ny);   
            }else{
             	chk_array[nx][ny] = true;   
            }
        }
    }
}

int main(int argc, char** argv)
{

	cin >> T;
    for(int i = 0; i < T; i++){
        count = 0;
         memset(array, 0, sizeof(array));
         memset(change_array, 0, sizeof(change_array));
         memset(chk_array, 0, sizeof(chk_array));
        
        cin >> N;
        for(int j = 0; j < N; j++){
        	for(int k = 0; k < N; k++){
            	cin >> array[j][k];
            }
        }
        change();
        
        for(int j = 0; j < N; j++){
        	for(int k = 0; k < N; k++){
                if(change_array[j][k] == 0 && !chk_array[j][k]){
                    count++;
                 	dfs(j,k);
                }
            }
        }
        
        for(int j = 0; j < N; j++){
        	for(int k = 0; k < N; k++){
                if(change_array[j][k] != 0 && !chk_array[j][k] && change_array[j][k] != -1 ){
					count ++;
                }
            }
        }
        	cout << "#" <<i+1<<" "<<count<<endl;
    }
}