잡다한 프로그래밍

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

1. 해결방법

SW expert 해결했던 문제 중 가능한 시험 점수라는 포스팅에서 해결했던 방법을 사용하면 해결할 수 있을 거라 생각했다. 이는 정확한 해결방법이었다

2. 코드

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

int total = 0;
int N = 0;
int K = 0;
int ary[20];
int temp[100000];
int sum = 0;

void check(){
    temp[0] = 1;
    sum = 0;
    
    for(int i = 0; i < N; i++){
     sum += ary[i];
        for(int j = sum; j>=0; j--){
            if(temp[j]){
                temp[j + ary[i]] += temp[j];
            }
        }
    }

}
int main()
{
    cin >> total;
    for(int i = 0; i < total; i++){
        memset(temp, 0, sizeof(temp));
        memset(ary, 0, sizeof(ary));      
        scanf("%d", &N);
        scanf("%d", &K);
        for(int j = 0; j < N; j++){
            scanf("%d", &ary[j]);
        }
        check();
        cout << "#" << i+1 << " " << temp[K] << endl;
    }
}

3. 주의사항

문제처럼 K의 범위를 1000으로 하면 런타임 에러가 발생하여 temp배열의 크기를 더 크게 설정해주었다

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

1. 해결방법

dfs를 활용하여 정해진 회문의 횟수만큼 방문했을 시 회문값에 일치하면 result개수를 늘리는 방법으로 해결하였다.

2. 코드

#include <iostream>
#include <string>
using namespace std;

int line = 0;
char ary[8][8];
char buf[10] = {};
int result = 0;
int dx[4] = {-1 , 1 ,0 , 0};
int dy[4] = {0, 0, -1, 1};
void check(int x, int y, int dept, int val) {
    buf[dept] = ary[x][y];
	if (dept == line-1) {
		string temp;
		string temp2;
		for (int i = 0; i < line; i++) {
			temp = temp + buf[i];
		}
		for (int i = line-1; i >= 0; i--) {
			temp2 = temp2 + buf[i];
		}
		if (temp.compare(temp2) == 0) result++;
	}
	else {
		int nx = x + dx[val];
		int ny = y + dy[val];

		if (nx < 0 || ny < 0 || nx >= 8 || ny >= 8)  return;
		else {
			check(nx, ny, dept + 1, val);
		}
	}
}

int main()
{
	for (int k = 1; k <= 10; k++) {
		cin >> line;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				cin >> ary[i][j];
			}
		}
		result = 0;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				for (int k = 0; k < 4; k++) {
					check(i, j, 0, k);
				}
			}
		}


		cout << "#" << k << " " << result / 2 << endl;
	}
	

}

3. 주의사항

dfs를 반복하면서 1번부터 4번까지 1,2,3,4 와 4번부터 1번까지 4,3,2,1을 두번 체크하기 때문에 결과값을 2로 나눠주면 올바른 결과 값이 나온다

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

1. 해결방법

먼저 N개를 2로 나눈 N/2의 몫을 P라 할 때 P가 처음 시작점이 될 것 이라고 생각했고, 첫번째 행부터 P번째 행까지는 -1, +1열까지 N부터 P번째 행까지는 +1 해가는 방식으로 2가지의 개수를 합치고 더해서 총 개수를 구하는 방식을 이용했다.

2. 코드

#include <iostream>

using namespace std;
int total;
int num;
int ary[49][49];
int sum = 0;
void check() {
	int center = num / 2;
	sum = 0;
	for (int i = 0; i < center; i++) {
		for (int j = center-i; j <= center+i; j++) {
			sum += ary[i][j];
		}
        for(int k = center - i; k <= center + i; k++){
            sum += ary[num-1-i][k];
        }
	}
            for(int m = 0; m<num; m++){
         	sum += ary[center][m];   
        }
}
int main()
{
    int temp = 0;
	cin >> total;
	for (int i = 0; i < total; i++) {
		cin >> num;
		for (int j = 0; j < num; j++) {
			for (int k = 0; k < num; k++) {
				scanf("%1d", &ary[j][k]);
			}
		}
		check();
		cout << "#" << i + 1 << " " << sum << endl;
	}
}

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

1. 해결방법

정해진 횟수만큼 최대값은 -1 최소값은 +1 반복문을 돌리면서 최대값과 최소값의 차이가 1 이하이면 리턴하게 하는 방법이 가장 적절하다고 생각했다. 예외가 하나도 발생하지 않아서 생각보다 쉬운 문제였다.

2. 코드

#include <iostream>
#include <algorithm>
int total;
int ary[100];
int result;

using namespace std;

void check() {
	int n = 0;
	while (n < total) {
		int max = *max_element(ary, ary + 100);
		int min = *min_element(ary, ary + 100);
		if (max - min <= 1) {
			break;
		}
		else {
			int maxindex = distance(ary, max_element(ary, ary + 100));
			int minindex = distance(ary, min_element(ary, ary + 100));
			ary[maxindex] = ary[maxindex] - 1;
			ary[minindex] = ary[minindex] + 1;
		}

		n++;
	}
}

int main()
{
	for (int i = 0; i < 10; i++) {
		cin >> total;
		for (int j = 0; j < 100; j++) {
			cin >> ary[j];
		}
		check();
		result = *max_element(ary, ary + 100) - *min_element(ary, ary + 100);
		cout << "#" << i + 1 << " " << result << endl;
	}
}

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

1. 해결방법

처음에는 for문을 이용해서 횟수만큼 가장 0번째값과 가장 큰 값을 교환, 이후 1번째 값과 가장 큰 값을 교환 .... 하는 방식으로 해결하려 했으나 배열의 수보다 회전의 수가 많아지거나 같은 자리가 교환 되어버리는 문제가 생겼다 따라서 dfs를 사용하여 모든 경우의 수를 비교하는 방법으로 해결하였다.

2. 코드

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

int total;
int num = 0;
string tmp;
int result;
void dfs(int x, int dept) {
	if (dept == num) {
		if (result < stoi(tmp)) {
			result = stoi(tmp);
		}
		return;
	}
	else {
		for (int i = x; i < tmp.size(); i++) {
			for (int j = i; j < tmp.size(); j++) {
				if (i == j) continue;
				if (tmp[i] <= tmp[j]) {
					swap(tmp[i], tmp[j]);
					dfs(i, dept + 1);
					swap(tmp[i], tmp[j]);
				}
			}
		}
	}
}
int main()
{
	cin >> total;
	for (int i = 0; i < total; i++) {
		result = 0;
		cin>> tmp;
		scanf("%d", &num);
		result = stoi(tmp);
		dfs(0, 0);
		printf("#%d %d\n", i + 1, result);
	}
}

3. 주의사항

같은 자리가 서로 바뀌는 것을 방지하기 위해 if (i == j) continue; 부분이 꼭 필요하다.

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

1. 해결방법

어떤 방법으로 해결을 할 수 있을지 몰라서 결국 문제를 찾았다 DFS를 활용한 백트래킹 방법으로 이를 해결하는 방법이 가장 일반화 되어있었고, DFS에서 가지치기를 하는방법이다.

2. 에러사항

가지치기를 하는 부분에서 예를들어 1행 1열에 체스가 놓여져 있다고 하면 2행에는 1행에놓여진 열, 열-1, 열+1 이 세가지를 피하면 해결 될 것이라고 생각했으나 이는 대각선을 처리하는 부분에 문제가 있었다. 대각선을 처리하는법은 행끼리의 차이와 열끼리의 차이가 같으면 대각선으로 판단하는 방법으로 해결했다.

3. 코드

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

int total;
int num;
int col[15];
int cnt;

bool check(int val) {

	for (int i = 1; i < val; i++) {
		if (col[i] == col[val]) {
			return false;
		}
		if (abs(val - i) == abs(col[val] - col[i])) {
			return false;
		}
	}

	return true;
}

void dfs(int row, int co) {

	if (row == num) {
		cnt++;
	}
	else {
		for (int i = 1; i <= num; i++) {
			col[row + 1] = i;
			if (check(row + 1)) {
				dfs(row + 1, i);
			}
			else {
				col[row + 1] = 0;
			}
		}
	}
	col[row] = 0;
}

int main()
{
	scanf("%d", &total);
	for (int i = 0; i < total; i++) {
		memset(col, 0, sizeof(col));
		cnt = 0;
		scanf("%d", &num);
		for (int j = 1; j <= num; j++) {
			col[1] = j;
			dfs(1, j);
		}
		cout << "#" << i+1 << " " << cnt << endl;
	}
}

링크

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;
}

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

1. 해결방법

모든 지점을 상 하 좌 우로 들리면서 7번째로 도착하면 set에 저장하면 자동으로 중복을 제거해 줄 수 있을 거라고 생각했다. 따라서 모든 지점을 상 하 좌 우로 들리는 방법을 코드로 구현하려 하였으나 결국 검색하여 찾아보니 dfs와 bfs방법을 사용한다고 한다. 이 문제의 해결방법으로는 dfs를 사용했고 dfs와 bfs는 따로 나중에 알고리즘에 추가하도록 할 예정이다.

2. 코드

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

int num = 0;
int arr[4][4];
set<int> setary;
void dfs(int x, int y, int val, int dept) {
	int nx[4] = { 0, 0, -1, 1 };
	int ny[4] = { -1, 1, 0, 0 };
	for (int i = 0; i < 4; i++) {
		if (dept == 7) {
			setary.insert(val);
			return;
		}
		int dx = x + nx[i];
		int dy = y + ny[i];

		if (dx < 0 || dx >= 4 || dy < 0 || dy >= 4) continue;
		else {
			dfs(dx, dy, val * 10 + arr[dy][dx], dept + 1);
		}
	}
}
int main()
{
	cin >> num;
	for (int i = 1; i <= num; i++) {
        setary.clear();
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> arr[j][k];
			}
		}
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				dfs(j, k ,arr[j][k], 1);
			}
		}
		cout << "#"<< i << " " << setary.size() << endl;
	}
}

main함수에서 dfs(j, k, arr[j][k], 1)이 부분을 처음에 0, 0 arr[j][k], 1로 하였다 이때 값이 항상 같은 오류가 생겼고 이를 j k로 수정하며 해결하였다.