잡다한 프로그래밍

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로 가능하다는걸 알았다. 어렵지 않았는데 왜 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. 해결방법

처음에 for문을 2번 돌려서 해결하려 했지만 오류가 있었고 다른 분의 코드를 참고하였다

점수가 3가지가 입력되었다면 1번부터 가능한 모든 점수를 구하고, 다음번에 2번째 점수를 1번째 경우에 수에 모두 더하고,,,, 이런 방식으로 해결하였다

2. 코드

#include <iostream>
#include <stdio.h>
#include<string.h>
using namespace std;
 
int total = 0;
int num = 0;
int ary[100];
int result[10001];
int temp;
int cnt;
 
int main()
{
    scanf("%d", &total);
    for (int i = 0; i < total; i++) {
        memset(result, 0, sizeof(result));
        memset(ary, 0, sizeof(ary));
        result[0] = 1;
        cnt = 0; temp = 0;
         
    scanf("%d", &num);
        for (int j = 0; j < num; j++) {
        scanf("%d", &ary[j]);
            temp += ary[j];
            for (int n = temp; n >= 0; n--) {
                if (result[n]) {
                    result[n + ary[j]]++;
                }
            }
                        result[ary[j]]++;
        }
        for (int i = 0; i < 10001; i++) {
            if (result[i] > 0)
                cnt++;
        }
 
        printf("#%d %d\n", i+1, cnt);
    }
    return 0;
}