재원블로그 재원블로그

이 문제는 구현 문제이다. 이 문제에서 시간 복잡도는 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, *2를 수행할 때 현재와 목적지와의 관계를 비교하지 않는 것이다. 이는 예제에서 말해주고 있다. 출발지가 5이고, 도착지가 17인데, 10에서 9로 가는 선택이 들어간다. 내가 했던 실수는 여기서 현재가 도착지보다 작을 경우, 0이 아니면 *2, +1 을 수행하고, 0이면 +1을 수행하는 식의 로직이 추가되었다는 점이다. 이러면 10에서 9로 가는 로직이 형성되지 않는다. 현재와 목적지까지의 상대 위치를 판단하지 않으면 큐에 너무 많은 숫자가 들어오게 되는데, 이를 방지하기 위해 다익스트라 알고리즘을 사용할 수 있다. 다익스트라를 이용하면 항상 현재 비용이 가장 적은 것부터 수행하기 때문에, 정답에 도착했을 때 바로 리턴해도 그것..

이 문제는 bfs를 이용해서 풀었다. visited 배열에 이미 벽을 하나 부쉈는지에 대한 여부 정보를 추가하면 쉽게 풀 수 있다. 결론적으로 가중치가 1인, 즉 단순히 이동한 거리에 대한 최소를 구하면 되므로 가장 먼저 (N, M) 에 도착한 것을 리턴해주어도 정답이 나올 수 있다. #include #include #include #include #include using namespace std; #define MAX 1000 #define INF 1000000000 #define NOT_DESTROY 0 #define DESTROY 1 int N, M; int matrix[MAX + 1][MAX + 1]; int dy[] = { -1, 0, 1, 0 }; int dx[] = { 0, -1, 0, 1..