문제https://www.acmicpc.net/problem/14889풀이시간을 너무 잡아먹은 문제였다. 초기 접근을 이상하게 해서 시간이 오래 걸린 점도 있었지만 재귀호출을 어려워하는 부분이 아직 있는 것 같다. dfs와 백트래킹을 통해서 모든 경우를 돌아보는 완전탐색 문제다.dfs로 스타트 팀으로 뽑을 선수 번호를 뽑는다스타트 팀으로 뽑은 선수가 N/2 명이 되면 두 팀의 능력치 차이를 구한다.위 과정을 반복한다.스타트 팀으로만 뽑는 이유는 어차피 뽑지 않은 선수는 링크 팀이기 때문이다. 소스코드에 주석을 보면 이해하기가 쉽다.소스코드#include #include #include using namespace std; #define MAX_SIZE 21 int n; bool is_used[MAX_SI..
문제https://www.acmicpc.net/problem/14503풀이한시간 반동안 비슷하게 푼 거 같았지만 결국은 테스트케이스도 못맞췄다.아직도 재귀호출을 구현하려면 머리가 아프다.dx[4], dy[4] 에 북(0), 동(1), 남(2), 서(3) 순으로 저장을 했다.현재 방향을 direction이라고 했을 때 북쪽을 보고 있는 경우를 제외하고 왼쪽 방향은 direction-1이기 때문에 이 점을 이용해 다음 방향을 정했다.다음 칸이 청소해야되는 칸일 경우에 그 칸으로 이동한 후에 나머지 방향의 탐색은 하지 않는다.다음 칸이 벽이거나 청소한 칸일 경우에는 방향만 바꿔주고 탐색을 계속 진행한다.네 방향 모두 검사를 마친 후는 모두 청소한 칸이거나 벽인 경우이기 때문에 방향을 유치한 채로 후진을 해줬다..
문제https://www.acmicpc.net/problem/14502풀이 재귀함수를 통해 벽 3개를 추가한다.벽이 3개가 쌓였을 때 BFS를 통해 바이러스를 퍼트리고 안전영역의 크기를 구한다.1로 돌아가 반복한다소스코드#include #include #include #include using namespace std; #define MAX_N 9 int n, m; int map[MAX_N][MAX_N]; int temp_map[MAX_N][MAX_N]; int ans; int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 }; vector virus; vector safety_Zone; void CopyMap(int(*a)[MAX_N], int(*b)[MAX_N]) {..
문제https://www.acmicpc.net/problem/2003풀이과정1차원 배열에서 각각 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 기법인 투 포인터(two pointers) 문제다.left ~ right 구간의 합을 확인하면 된다.(93%,1초) 에서 “틀렸습니다”가 떴다. 왜 그런가 찾아봤더니 한 가지 예외처리를 해줘야되는 문제였다.만약 left+1 이 right보다 커질 경우에는 left와 right의 자리를 바꿔줘야된다.소스코드 #include using namespace std; #define MAX_N 10001 int n, m; int a[MAX_N]; int ans; void solution() { int left = 0, right = 0,now_Sum..
문제https://www.acmicpc.net/problem/1182풀이과정recursion을 통해 간단하게 해결할 수 있는 문제다. 입력 된 숫자들을 더하는 경우, 더하지 않고 그냥 넘어가는 경우 두 가지로 나누어서 재귀호출을 하면 된다.소스코드#include using namespace std; #define MAX_N 21 int n, sum; int num[MAX_N]; int ans; void sub(int i, int prev_Sum) { // index를 끝까지 했으면 종료 if (i == n) { // sum과 같으면 ans++ if (prev_Sum == sum) ans++; return; } // 숫자를 사용하는 경우 sub(i + 1, prev_Sum + num[i]); // 사용하지..
문제https://www.acmicpc.net/problem/1987풀이과정입력으로 알파벳 대문자로 이루어진 보드판이 주어진다. (0,0) 부터 문제에서 주어진 규칙에 따라 인접한 상하좌우로 이동할 수 있는 최대칸 수를 출력해야하는 문제다.DFS로 접근을 했고 처음에는 문제를 잘못보고 이전 알파벳하고 방문하는 알파벳만 다르면 방문할 수 있는 줄 알았다.문제를 자세히 보면 밟아온 보드판에서 사용된 알파벳은 다시 밟을 수 없다고 한다.그래서 알파벳의 사용여부를 체크하는 배열을 만들어 DFS를 돌렸다.소스코드#include #include #include using namespace std; #define MAX 21 int r, c; char alpha[MAX][MAX]; // 입력되는 보드판 bool ch..
문제https://www.acmicpc.net/problem/2580풀이과정스도쿠를 완성하는 문제이다. DFS와 백트래킹을 통해 가능한 수를 구해서 완성되면 출력한다. 스도쿠의 규칙은 열, 행 , 3x3 정사각형 칸에 1~9까지의 숫자가 한개씩만 존재해야한다.이러한 규칙에 따라서 열, 행, 정사각형의 어떤 숫자(1~9)가 존재하는지 체크하는 배열을 만든다.모든 경우의 수를 다 해볼 수 있지만 그렇게 하면 시간초과가 뜰 수 있다.소스코드#include using namespace std; #define MAX_NUM 10 int sudoku_size = 9; int sudoku[MAX_NUM][MAX_NUM]; bool chk_row[MAX_NUM][MAX_NUM]; // 행에 숫자(1~9)가 존재하는지 ..
문제https://www.acmicpc.net/problem/1759풀이과정문제에서 만들어야 될 암호의 길이와 사용할 수 있는 알파벳의 종류가 주어진다.입력으로 주어지는 사용할 수 있는 알파벳들을 배열로 저장하였고, 그 배열의 인덱스를 하나씩 늘려가며 사용할지 안할지 결정해 암호를 만드는 recursion 함수를 구현했다.소스코드의 주석을 보면 이해하기가 쉽다.소스코드#include #include #include #include using namespace std; bool chk(string &password) { int ja = 0, mo = 0; int length = password.length(); for (int i = 0; i < length; i++) { char c = password[..
문제https://www.acmicpc.net/problem/2251풀이과정A, B, C 세 가지 물통의 부피가 주어진다. 문제에서 물통 C는 처음부터 꽉 차있다고 주어진다. 문제에서 원하는 답은 물통 A가 비어있을 때 C에 남아있는 물의 양이다. 문제에서 물이 옮겨담기는 과정에서 손실되는 경우는 없다고 했다. 그러므로 A, B 물통에 남아있는 물의 양만 있다면 물통 C에 남아있는 물의 양도 구할 수 있다. c(물통 C의 남은 물의 양) = C(물통 C의 부피) - a(물통 A의 남은 물의 양) - b(물통 B의 남은 물의 양) 물을 옮겨담는 경우의 수는 총 6가지다. A -> BA -> CB -> AB -> CC -> AC -> B모든 경우를 탐색해보기 위해 BFS를 이용하고 물통 A, B의 남은 물의..
문제https://www.acmicpc.net/problem/1525풀이의 핵심 입력을 2차원 배열로 저장하지 않고 입력을 받아 하나의 정수로 만든다.BFS를 이용해 123456789 까지 탐색한다.상하좌우를 검사해서 바꿀 수 있으면 바꾼다.dist[num] 에 연산횟수를 저장한다.소스코드#include #include #include #include using namespace std; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n = 3; int start = 0; // 2차원 배열이 아닌 하나의 정수로 나타낸다. (0을 9로..