재원블로그 재원블로그

이 문제는 구현 문제이다. 이 문제에서 시간 복잡도는 13Cm * 2N * m 이다. 13C6이나 13C7 일 때 1,719로 가장 큰데, 이 때도 약 100만 밖에 되지 않으므로 충분히 1초 안에 풀 수 있다. 처음에는 bfs를 생각했으나, 치킨 거리를 수식으로 한번에 알 수 있으므로 시간 복잡도만 늘리는 꼴이었다는 것을 깨달았고 단순히 구현하여 해결할 수 있었다. 집과 치킨집을 입력에서 받아 배열로 따로 저장한 뒤, 치킨집에서 M개를 선택해 치킨 거리를 측정하는 방식으로 구현했다. #include #include #include #include using namespace std; #define MAX 50 #define INF 1000000000 int N, M; vector house; vecto..

이 문제는 구현 문제이다. 3세대 드래곤 커브를 보면 규칙성을 찾을 수 있다. (0,0)부터 시작해서, 오-위-왼-위 + 왼-아-왼-위 순으로 움직이게 된다. 오위왼위를 역순으로 배열하면 위왼위오이고, 이를 통해 이전 드래곤 커브에서 위 - 왼, 왼 - 아, 오 - 위, 아 - 오 로 매핑되는 것을 발견할 수 있다. 2세대 드래곤 커브인 오위왼위를 보면 오-위 + 왼-위 또한 같은 방식으로 매핑됨을 알 수 있다. 이를 통해 10세대까지의 드래곤 커브를 반복문으로 미리 만들어놓을 수 있다. 드래곤 커브만 만들면 구현은 아주 쉽게 된다. 입력받은 N으로 루프를 돌면서 드래곤 커브를 만들고, 다 만든 뒤에는 네 꼭짓점이 모두 드래곤 커브에 속하는지 확인만 하면 된다. #include #include #incl..

이 문제는 브루트포스와 백트래킹을 이용하는 구현 문제이다. 이 문제가 브루트포스 문제인것까지 생각했지만, 구현에서 막혔다. 어려운 구현 문제일수록 구현을 최대한 쉽게 하려는 노력이 필요한 것 같다. #include #include using namespace std; bool connected[100][100]; // n : 세로줄, m : 가로줄 개수, h : 가로 위치의 개수 int n, m, h; int answer = INT32_MAX; bool isCorrect() { for (int i = 1; i > m >> h; for (int i = 0; i > a >> b; connected[b][a] = true; } func(1, 0); if (ans..

이 문제는 구현 문제이다. 각 2N개의 길이 경사로를 설치하여 갈 수 있는 길인지를 체크하는 문제이다. N이 100으로 아주 작기 때문에 요구사항만 구현하면 문제가 풀린다. 현재와 다음 블럭을 비교했을 때 같은지, 더 높은지, 더 낮은지에 대한 분기문을 작성하여 문제를 해결했다. 다만 주의할 점은 경사로를 설치할 수 있는 높이 차는 최대 1이기 때문에 이를 체크해주지 않으면 오답이 나온다. #include #include #include using namespace std; #define MAX 100 int N, L; int matrix[MAX][MAX]; int absolute(int num) { if (num < 0) { return -num; } return num; } bool rowCheck(..

이 문제는 시뮬레이션 문제이다. 시뮬레이션 문제 특성상 문제 요구사항이 복잡한 대신 구현만 제대로 되면 정답이 바로 나온다. 주사위를 길이가 6인 배열로 구성하고, 각 인덱스에 대해 실제 위치를 상수로 정해서 가독성을 높였다. 주사위는 6개 면밖에 없기도 하고, 규칙성을 빠르게 찾아내지 못해 굴리는 방향에 따라 직접 수정을 해주는 방식으로 구현했다. #include #include using namespace std; #define MAX 20 #define RIGHT 1 #define LEFT 2 #define UP 3 #define DOWN 4 #define ABOVE 0 #define BELOW 1 #define EAST 2 #define NORTH 3 #define WEST 4 #define SO..

이 문제는 시뮬레이션 문제이다. 입력 배열이 최대 50 x 50 으로 작기 때문에 구현만 한다면 정답이 나오는 문제이다. 1. 현재 칸이 청소되지 않은 경우, 현재 칸 청소 2. 현재 칸 주변 4칸 중 청소되지 않은 빈칸이 없다면 2-1. 바라보는 방향 유지한 채로 한칸 후진할 수 있다면 한칸 후진 후 1번 돌아감 2-2. 바라보는 방향 뒤쪽이 벽이라 후진 불가능하면 작동 멈춤 3. 현재 칸 주변 4칸 중 청소되지 않은 빈칸이 있다면 3-1. 반시계 방향으로 90도 회전 3-2. 바라보는 방향 기준 앞쪽 칸이 청소되지 않은 빈칸일 경우 한 칸 전진 3-3. 1번으로 돌아감 이라는 조건을 만족하도록 로직을 구성하면 바로 정답이 나온다. #include #include using namespace std; ..

이 문제는 구현 문제이다. 문제 제목 보고 1억 * 1억 배열이라 다른 방법을 사용할 줄 알았는데 입력으로 주어지는 e가 최대 5백만이라 배열로 만들 수 있었다. 가장 처음 나오는 이중 for문에 5,000,000을 넣고 카운트해보면 약 7,800만 정도의 연산을 수행하게 된다. 따라서 1초 안에 cnt를 모두 셀 수 있다. 범위를 세는 부분이 언뜻 시간을 초과할 것처럼 보이지만, starts 배열을 내림차순 정렬한 뒤 각 루프마다 구간을 계산하면 이전 결과를 활용할 수 있어 O(N)이면 해결된다. 이 때 정렬을 해도 원래 위치를 알 수 있어야 하기 때문에 pair를 사용하였다. #include #include #include #include #include using namespace std; #def..

이 문제는 bfs, 트리를 이용해서 풀었다. 이 문제에서 노드의 수가 n일 때 간선의 수가 n - 1개이고, 모든 임의의 두 점은 연결되어있으므로 입력 그래프는 트리이다. 트리는 아무 점이나 루트로 잡아도 트리이므로, 1을 루트로 잡았다. bfs를 이용해서 노드들의 depth를 계산한다. bfs 이후에는 depth가 깊은 순서대로 내림차순 정렬 후 루프를 돌린다. depth가 가장 깊은 리프 노드부터 자신의 부모를 확인한다. 이 때 자신이 이미 켜져있는 경우에는 continue한다. 만약 자신의 부모가 등대가 켜져있지 않다면 켜주고 answer++하는 방식으로 정답을 구할 수 있다. 문제에서 입력 그래프가 트리일 경우에는 bfs나 dfs를 이용한 풀이가 적용되는 경우가 많았던 것 같다. #include ..