기록을

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

연산자의 수가 가령 1,5,0,3

이렇게 주어지면 나는 새로운 벡터에 0을 1개, 1을 5개, 3을 3개 추가하고, 그 백터를 이용해서 순열을 돌렸다.

이 과정에서 중복도 발생하고, set을 사용해서 중복을 처리해주더라도 연산 시간이 소모되기 때문에 시간초과가 나는 것 같다.

따라서, 그냥 1,5,0,3 상태에서, 내가 무언가를 뽑으면 그 원소에 1을 더하거나 빼주고, 양수일 경우에만 뽑을 수 있게 하는 방식으로 DFS를 구현해야 통과할 수 있을 것 같다.

아래는 시간 초과를 받은 코드이다.

https://www.welcomekakao.com/learn/courses/30/lessons/42891

k번 순회하도록 해서 정확도밖에 맞추지 못한 코드이다.

순회 방법을 줄일 아이디어가 필요하다.

처음에 든 생각은, 배열에서 0이 아닌것의 개수와, 배열의 최솟값을 곱하면 이만큼을 한 번에 먹는 것으로 처리할 수 있다는 것.

다른 생각은 정렬해서 k보다 작을동안 묶어서 빼준 이후에, 한 번에 먹을 수 있는 게 k보다 커지면 다시 순회하는 방법이 있을 것 같다.

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

4방향 dfs 탐색을 활용해서 y가 네개 이하인 경우에만 결과에 포함시키려고 했다.

이렇게 접근하면 자리에 앉아 있는 사람이 y파인지s파인지 말고는 개별적으로 구분할 수 없기 때문에 각자 결과로 나온 문자열을 구분하지 못한다.

가령 sysysys라는 문자열은 맞는 결과이지만, 행렬에서 어떤 위치의 성분을 가져다가 저걸 만들어냈느냐에 따라서 서로 다른 문자열일 수도 있고 같은 문자열일 수도 있다.

아래는 틀린 코드이다.

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

퀸이 올라올 수 없는 곳의 위치를 체스판 한 칸 한 칸으로 관리하려고 했다.

그래서 2차원 배열을 활용했는데

초반의 생각은 이러했다.

가령 1,0에 퀸을 놓으면 1,0이 포함된 행과 열 그리고 두 개의 대각선에 퀸을 놀 수 없다.

이때 1,2는 둘 수 없는 위치이다. 그런데 2, 2는 둘 수 있는 위치이고, 2,2에 퀸을 두고 또 2,2를 둠으로써 둘 수 없는 위치를 잡고 나서 재귀를 빠져나올 때, 2,2의 행과 열 그리고 두 대각선의 bool 값을 모두 변경해버리면 1,1가 막고 있었던 것이 풀리게 되어서 제대로 된 연산이 되지 않는다.

따라서 좌표 하나하나를 관리할 게 아니라, 열과 행 그리고 대각선들로 사용중 여부를 관리하는 배열을 잡아야 한다.

#include<iostream>
using namespace std;
int N, m[15][15];
bool isused[15][15];
int cnt = 0;
void usage(int i, int j, bool ctr) {
	isused[i][j] = ctr;
	if (ctr) {
		printf("퀸위치: %d %d'\n", i, j);
	}
	for (int k = 0; k < N; k++) {
		isused[i][k] = ctr;
		isused[k][j] = ctr;
	}
	for (int l = 0; l < N; l++) {
		for (int m = 0; m < N; m++) {
			if (l + m == i + j) isused[l][m] = ctr;
			if (l - m == i - j) isused[l][m] = ctr;
		}
	}
}
void func(int k) {
	if (k == N+1 ) {
		cnt++;
		
		return;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!isused[i][j]) {
				usage(i, j, true);
				printf("%d %d에 퀸추가\n", i, j);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						cout << isused[i][j] << ' '; 
					}cout << '\n';
				}
				cout << '\n'<<'\n';
				func(k + 1);

				//isused[i][j] = false;
				usage(i, j, false);
				printf("%d %d에 퀸제거\n", i, j);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						cout << isused[i][j] << ' ';
					}cout << '\n';
				}
				cout << '\n' << '\n';
			}
		}
	}
}
int main(void) {
	cin >> N;
	func(1);
	cout << cnt << '\n';
	return 0;
}