재원블로그 재원블로그

이 문제는 구현, 시뮬레이션 문제이다. 구현이 매우 까다로운데, 큐브가 매우 작아 구현만 하면 정답이 나온다. 중요한 포인트가 몇 가지 있는데, 첫번째는 면의 기준을 잘 정하는 것이다. 각 면에 대한 배열을 만들고, 각 면의 상하좌우에는 어떤 면이 존재하는지를 먼저 정하고 구현에 들어가야한다. 두번째로는 각 면을 정면으로 봤을 때 상하좌우 면의 방향을 잘 확인하는 것이다. 돌렸을 때 역방향인 경우에는 방향을 바꾸어서 집어넣어줘야 제대로 값이 들어가게 된다. 마지막으로 옆면 뿐만 아니라 정면도 같이 돌려줘야 한다. 옆면에 너무 집중하다보니 앞면도 돌려줘야 한다는 사실을 까먹는다. 계속 정답이 안 나오던 문제가 앞면까지 돌려주자마자 바로 정답이 나왔다. #include #include #include usi..

이 문제는 구현, 시뮬레이션 문제이다. 입력이 작은 편이고 요구사항이 매우 복잡하기 때문에 구현만 된다면 정답을 받을 수는 있다. 어항을 위에 쌓는 기능이 있어야하기 때문에 deque 배열로 어항을 표현했다. 2개 이상 쌓여있는 마지막 어항의 높이와 오른쪽에 남아있는 어항 개수를 비교하면 공중부양은 쉽게 구현할 수 있다. 문제는 bfs 함수인데, 이름과 다르게 완전 탐색으로 구현해야한다. 동시에 일어나는 것을 구현하기 위해서는 bfs로는 도저히 나오지 않는다. 따라서 이중 for문으로 구현해야한다. 또한 상하좌우를 모두 체크하면 중복으로 카운팅이 들어가므로 오답이 나온다. 따라서 아래, 오른쪽만 확인하는 방식으로 해결할 수 있었다. 가장 문제가 되는 것은 2차원 배열의 높이인데, 멋 모르고 N / 2로 ..

이 문제 또한 백트래킹으로 풀었다. 연산 수는 최대 20C10 * 10 * 10 이므로 충분히 1초 안에 풀 수 있다. 로직은 절반을 선택하고, 스타트 팀과 링크 팀의 능력치를 구해 차이를 리턴해주면 된다. #include #include #include using namespace std; #define MAX 20 #define INF 1000000000 int N; int S[MAX][MAX]; void input() { cin >> N; for (int i = 0; i > S[i][j]; } } } vector makeLink(vector &start) { vector visited(N, false); for (i..

이 문제는 완전 탐색으로 풀었다. 최대 숫자의 개수가 11개이므로, 연산자의 개수는 최대 10개가 된다. 따라서 10개의 자리에 각 연산자를 집어넣으므로 10! 의 최대 수행 시간이 걸려 1초 안에 풀 수 있다. 로직은 매우 간단하다. 연산자를 N - 1개 선택하고, 모두 선택했을 때 계산을 진행해서 답을 구해주면 된다. #include #include #include using namespace std; #define MAX 11 #define PLUS 0 #define MINUS 1 #define MUL 2 #define DIV 3 #define MAX_INIT -1000000001 #define MIN_INIT 1000000001 int N; int A[MAX]; vector oper; vector..

이 문제는 백트래킹으로 풀 수 있다. 입력 크기 N이 15로 매우 작다. 따라서 백트래킹으로 풀었다. 0일부터 시작해서, 현재 상담을 할지 말지를 결정하는 로직으로 재귀를 구성하면 쉽게 풀 수 있다. #include #include using namespace std; #define MAX 15 int N; int T[MAX]; int P[MAX]; void input() { cin >> N; for (int i = 0; i > T[i] >> P[i]; } } int solve(int day) { if (day == N) { return 0; } int result = 0; // jump if (day + T[day]

이 문제는 간단한 구현 문제이다. 매우 간단해보이는데 생각보다 정답률이 낮았다. 문제는 아주 간단한데, 총감독관을 각 방에 집어넣은 뒤 남은 인원을 부감독관으로 빼주면 된다. 여기서 문제는 시험장의 개수가 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..