재원블로그 재원블로그

이 문제는 간단한 구현 문제이다. 매우 간단해보이는데 생각보다 정답률이 낮았다. 문제는 아주 간단한데, 총감독관을 각 방에 집어넣은 뒤 남은 인원을 부감독관으로 빼주면 된다. 여기서 문제는 시험장의 개수가 100만이고, B, C가 1이고, 응시자의 수가 모두 100만이면 100만 * 100만의 결과가 나오므로 오버플로우가 발생하는 것이다. 이를 해결하기 위해 정답 변수의 타입을 long long으로 하면 쉽게 풀린다. #include using namespace std; #define MAX 1000000 typedef long long LL; int N, B, C; LL students[MAX]; void input() { cin >> N; for (int i = 0; i < N; i++) { cin ..

이 문제는 bfs를 이용한 구현 문제이다. 공간의 크기가 아주 작기 때문에, 구현만 제대로 해내면 정답이 나온다. 처음에는 거리가 가까운 물고기를 찾을 때 BFS 한번으로 찾아냈지만, 이 경우 예제 4번에서 60이 아닌 56이 나오게 된다. bfs에서 상좌우하 순으로 탐색하는 방식이었지만, 이 경우 왼쪽 아래 (2초) 물고기와 오른쪽 두칸 (2초) 물고기 중 왼쪽 아래 물고기를 선택하게 된다. 따라서 먼저 먹을 수 있는 물고기를 루프로 찾고, 그 물고기의 좌표로 가는 최단 거리를 bfs로 계산하는 방식으로 구현했다. 이 경우 N^6 번, 즉 최대 6,400만 정도의 연산을 수행하므로 1초 안에 풀 수 있다. #include #include #include using namespace std; #defin..

이 문제는 bfs를 이용한 문제이다. 입력이 작기 때문에 구현만 하면 정답이 나오는 문제라고 생각했다. 국경선을 여는 것을 bfs를 이용해서 같은 연합에 속한 pair들을 담은 vector를 리턴하도록 만들었다. 이 때, 연합의 배열의 size가 N * N 이라는 것은 2개 이상 연결된 연합이 전혀 없다는 뜻이므로, 종료 조건이 된다. 이 배열을 사용하여 값을 계산하고, world 배열에 반영해주면 문제가 풀린다. #include #include #include #include #include using namespace std; #define MAX 50 int N, L, R; int world[MAX][MAX]; int dy[] = { -1, 0, 1, 0 }; int dx[] = { 0, -1, 0..

이 문제는 구현 문제이다. 이 문제에서 시간 복잡도는 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..