With The Lights Out

다음 순열을 구하는 문제이다. 처음에는 백트래킹, dfs, 재귀 를 전부 사용해 모든 순열을 찾아가다가 조건에 맞으면 출력하는 방식을 선택하려고 했는데, 범위가 10000 까지이므로 시간 초과가 났다.   #include #include #include #include using namespace std;int N;vector v;vector input_v;bool visited[100001] = {false};bool same = false;void dfs(int input){ if(input == N) { if(same) { for(auto i : v) { cout > N; int tmp; ..

앞의 문제들과 똑같이 풀이를 한다. 그러나 중복되는 수열을 여러 번 출력하면 안된다.  따라서 set 을 사용하여 풀이했다. 처음에는 unordered_set 을 사용해야 하나 하고 생각했었지만 순회를 전부 돌기 때문에 상관이 없다는 것을 이내 깨달았다.  #include #include #include #include using namespace std;vector v;vector input_v(10);set> s;bool visited[10] = { false };int N, M;void dfs(int input){ if (input == M) { s.insert(v); /* for (auto i : v) { cout >..

dfs, 백트래킹, 재귀 를 사용해 푸는 문제이다.DFS - 깊이우선 탐색으로 수열을 제공받는 길이 M 까지 출력하기 위해서 사용하는 알고리즘 백트래킹 - 해를 찾는 도중, 해가 아니어서 막히면 다시 돌아가서 해를 찾는 방법 재귀 - 함수 내에서 자기 자신을 다시 호출하는 함수 처음에 dfs 함수를 0 을 넣어 호출해 1 2, 1 3, 1 4, 2 1 .... 등등 출력할 수 있도록 재귀함수 탈출조건을 명시해준 후 ( 함수 인풋이 M과 같으면 == 수열의 개수가 M개로 채워지면) 탈출 시에는 벡터에 담아두었던 원소를 전부 출력한다. 탈출조건 만족 못할 시에는 순회 하면서 벡터에 넣어주고 dfs(+1) 만큼 재귀호출 해준다.    #include #include #include #include using ..

음... 영양가 하나도 없는 밥을 억지로 우겨넣는 느낌의 문제였다.배열 초기화만 할 줄 알면 쉽게 풀 수 있다.   #include #include using namespace std;int a[1001][1001];int p[501][501];int t[20][4][4] = { { {1,1,1,1}, {0,0,0,0}, {0,0,0,0}, {0,0,0,0} }, { {1,0,0,0}, {1,0,0,0}, {1,0,0,0}, {1,0,0,0} }, { {1,1,0,0}, {1,1,0,0}, {0,0,0,0}, {0,0,0,0} ..

좀 멍청하게 풀었나 해서 다른 사람들의 풀이를 확인 해 보았었는데, 메서드 화 하지 않고 푼 것 말고는 딱히 다른 효율적인 방법이 없었다. 어짜피 브루트 포스로 풀이하는 것이기도 했고, 다음 문제로 넘어가기로 했다.  #include #include #include using namespace std;int N;char a[51][51];int main() { cin >> N; for (int i = 0; i > a[i][j]; } } int max = 0; for (int i = 0; i