개발기록 개발기록

www.acmicpc.net/problem/1074 문제를 작은 문제로 쪼갤 수 있음을 알 수 있다. #include #include #include using namespace std; int n; int r, c; int res; void find(int len, int sy, int sx, int startNum) { if (sy == r && sx == c) { res = startNum; return; } int half = len / 2; int y = sy + half; int x = sx + half; if (r = x) { find(half, sy, x, startN..

www.acmicpc.net/problem/1175 중복체크를 위한 상태공간을 정의해야 합니다. 탐색이 발산적으로 이루어지므로 목표지점 1을 방문할 때, 목표지점 2의 경로를 지나갈 수 있습니다. 따라서 이 두 개는 따로 체크되어야 합니다. 그리고 방향은 매시간 달라지므로 어떤 방향으로 나가냐(혹은 들어오냐)에 따라 체크가 따로 되어야 합니다. 따라서 상태공간을 이루는 요소로 좌표, 방향, 1의 방문 여부, 2의 방문 여부 입니다. #include #include #include #include #include #include using namespace std; #define MAX 50+1 struct point { int y, x, dir, cnt; bool cVisited = false, dVis..

www.acmicpc.net/problem/9328 탐색이 1번으로 끝나지 않습니다. 탐색 도중 열쇠를 얻게 되면 탐색할 수 있는 공간이 늘어나기 때문이죠. 따라서 더 이상 열쇠를 얻지 않을때까지 탐색을 반복해주면 됩니다. #include #include #include #include #include using namespace std; #define MAX 1005 struct point { int y, x; }; int test; int n, m, res; char map[MAX][MAX]; bool visit[MAX][MAX]; string key; int dy[] = { 1, -1, 0, 0 }; int dx[] = { 0, 0, 1, -1 }; void print_map() { for (int..

www.acmicpc.net/problem/16952 방문체크를 하기 위해 상태공간을 정의할 필요가 있다. 상태공간에 들어갈 요소로 좌표, 현재 번호, 말의 종류가 있겠다. 문제에서 요구하는 값은 시간과 바꿈수이다. 이 둘 모두가 최소로 나와야 하므로 두 개가 비교해줄 필요가 있다. 이를 위해 pair를 사용했다. #include #include #include #include #include using namespace std; #define MAX 10 + 1 struct point { int y, x; int kind, num; int time, change; }; int n, sy, sx; int map[MAX][MAX]; pair visited[MAX][MAX][150][3]; int dy[] ..

www.acmicpc.net/problem/16920 범위 크기만큼 bfs를 돌리면 확장 1번이 진행된다. 모든 플레이어에게 개인 큐를 지급해서 범위만큼 돌리도록 한다. #include #include #include using namespace std; #define MAX 1000 + 1 struct point { int y, x; }; int n, m, pCnt; bool endCondition; int map[MAX][MAX]; int range[10]; int res[10] = {0, }; int dy[] = { 1, -1, 0, 0 }; int dx[] = { 0, 0, 1, -1 }; queue q[10]; void printMap() { for (int i = 0; i < n; i++) {..

www.acmicpc.net/problem/8111 1. 1부터 시작하여 뒤에 1, 0을 달아주며 완전탐색을 한다. - 탐색 시, 오버플로우가 나지 않도록 (현재 숫자 % 목표 숫자)를 넣어주도록 한다. - 탐색 종료 후, 만든 숫자를 출력해야하므로 트리를 만들면서 탐색한다. 2. 탐색 종료 후, 트리를 바텀에서부터 탑으로 향하며 만든 숫자를 출력한다. #include #include #include #include #include #include using namespace std; #define MAX 20000 + 1 int test; int n; int parent[MAX]; char s[MAX]; void bfs() { queue q; bool visit[MAX]; memset(visit, fa..

www.acmicpc.net/problem/1062 백트래킹으로 풀 수 있는 문제이다. 가르칠 단어를 정하고 가르칠 수 있는지에 대한 여부를 확인할 때, 비트마스킹을 이용해 단어를 int형 변수에 저장하면 시간최적화가 가능하다. #include #include #include using namespace std; #define MAX 50 int n, k; bool visit[27]; int res; string S[MAX+1]; void input() { cin >> n >> k; for (int i = 0; i > S[i]; } } int check_same() { int cnt = 0; for (int i = 0; i < n; i++) { int len = S[i].l..

www.acmicpc.net/problem/4577 이동연산을 구현할때, b. B. w. W를 그대로 사용했으면 구현이 복잡해졌을 것이다. 문제를 분해하여 단순하게 생각하기 상태를 복사시켜서 저장해놓기 #include #include #include #include using namespace std; struct point { int y, x; }; int py, px; int n, m; char tmap[17][17]; char map[17][17]; int dy[] = { -1, 1, 0, 0 }; int dx[] = { 0, 0, -1, 1 }; int Dir[51]; string tDir; vector target; void print_map() { cout > n >> m; if (n == 0..