1일1알

처음 풀어보는 플래티넘 등급의 문제이다. 푸는 방법을 생각해내는 게 쉽지 않았다. 첫 번째 줄의 전구를 누르거나 누르지 않는 모든 경우 : 2^10 = 1024 이 경우들에서 시작하여 다음 줄에서부터는 자신의 위쪽이 켜져 있으면 끄고, 아니면 넘어간다. = 10) continue; if (nextCol = 10) continue; tmp_board[nextRow][nextCol] = !tmp_board[nextRow][nextCol]; } } void BT(int idx) { if (idx > 9) { bool isAns = true; int cnt = 0; vector tmp_board(10, vector(10)); for (int i = 0; i < 10; i++) { f..

1. 배양액을 뿌릴 수 있는 땅의 그룹을 만든다. (예제 2의 입력을 예로 들면 (0, 0), (2, 0), (2, 2)) 2. 배양액을 뿌릴 수 있는 땅의 그룹 중 r + g 만큼의 땅의 그룹들을 백트래킹을 이용하여 모두 찾는다. (예제 2의 입력을 예로 들면 g는 2, r는 1이어서 r + g는 3 이기 때문에 1번과 같다.) (만약 g = 1, r = 1 이었다면 r + g = 2 이기 때문에 (0, 0), (2, 0) 과 (0, 0), (2, 2) 과 (2, 0), (2, 2) 세 가지 경우가 나옴) 3. 2에서 찾은 그룹을 r 그룹과 g 그룹으로 나눈다. (예제 2의 입력을 예로 들면 g는 2, r는 1이기 때문에 g : (0, 0), (2, 0) , r : (2, 2) g : (0, 0), (..

1. 백트래킹을 이용하여 7명의 학생을 모은 그룹을 모두 탐색한다. 2. 7명이 전부 붙어있는지 bfs를 이용해 확인한다. 3. 7명이 전부 붙어있다면 이다솜파의 학생이 4명 이상인지 확인해서 맞다면 ans를 1 증가시킨다. tip : n번째 학생이라면 n/5, n%5를 통해 행과 열을 알아낼 수 있다. (n은 0부터 시작) 예를 들어 7번째 학생이라면 7/5 , 7%5 이므로 학생의 위치는 (1, 2) 라는 것을 알 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ..

우선 백트래킹을 이용하여 나열 가능한 모든 경우의 수를 탐색하였다. 탐색을 마칠 때, 숫자를 담는 벡터와 연산자를 담는 벡터 두 개를 새로 만들었다. 숫자를 담는 벡터에는 이어붙일 수 있는 숫자들을 넣고, ( 1+2 3 이면 1, 23 이 들어감) 연산자를 넣는 벡터에는 +와 - 연산자만 넣었다. 그러면 예를들어 1+2 3-4 5 인 경우에는 숫자를 담는 벡터에는 1, 23, 45가 들어가고 연산자를 담는 벡터에는 +, - 이 들어간다. 새로 만든 두 벡터를 이용해 값을 계산해서 0이 되는 경우만 출력하도록 하였다. #include #include #include #include #include #include #include #include #include #include #include #includ..

패턴은 * 한개와 알파벳들로 이루어져 있고, * 은 문자열의 시작과 끝에 있지 않기 때문에 무조건 ~~~*~~~ 이런 형태로 이루어져 있다는것을 알 수 있다. 그렇기 때문에 파일과 패턴을 맨 앞부터 * 전까지 비교하고, 맨 뒤부터 * 뒤까지 비교해서 하나라도 다르면 일치하지 않는다. 그리고 고려해야될게 하나 더 있는데, 만약 패턴이 abc*abdef 이고, 파일이 abcdef 라면 위의 비교에서는 전부 같지만, 일치하지는 않는 파일이다. 그렇기 때문에 패턴의 길이 - 1 (*이 있어서 1을 빼줌) 는 파일의 길이보다 작거나 같아야 한다. #include #include #include #include #include #include #include #include #include #include #inc..

각 사람이 3장의 카드를 뽑는 경우의 합을 백트래킹을 통하여 모두 구하고, %10 연산을 통해 일의 자리만 비교하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; vector v(1001, vector(5)); int ans = -1; int maxV = -1; void BT(int num, int idx, int cnt, int sum) { if (cnt >= 3) { int res = sum % 10; if (res >= maxV) { maxV = ..