재원블로그 재원블로그

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 입력 배열의 최대 크기가 16 x 16으로 작긴 하다. 그러나 혹시 모를 시간 초과를 대비하여 다이나믹 프로그래밍으로 확실하게 시간을 줄였다. dp[y][x][direction] : (y, x) 위치에서 direction으로 파이프가 놓여져 있을 때 이동시킬 수 있는 경우의 수 로 놓아서 문제를 쉽게 해결할 수 있었다. #include #include #include #include using namespace std; #define MAX 16 #define GARO 0 #define DAEGAK 1 #define SERO 2 int N; int house[MAX + 1][MAX + 1]; int dp[MAX + 1][MAX + 1][3]; void i..

이 문제는 bfs를 이용해서 푸는 문제이다. 입력으로 주어지는 2차원 배열이 최대 100 x 100 이므로 O(N^2) 알고리즘일 경우 최대 10,000번의 반복을 수행할 수 있다. 모눈종이의 가장자리에는 치즈가 놓이지 않기 때문에, 치즈가 아무리 많아도 98 x 98 크기를 넘을 수 없다. 각 가장자리부터 한 반복문 당 한 겹씩 사라지므로 충분히 시간 안에 풀 수 있다. 가장 핵심은 외부 공기와 내부 공기를 구분하는 것인데, 이를 위해 가장자리에는 치즈가 놓이지 않는다는 가정을 사용했다. 이는 가장자리는 무조건 외부 공기라는 말이 된다. 따라서 (0,0) 에서부터 bfs를 시작하여 치즈를 만나면 멈추는 방식으로 구현하면 외부 공기들을 알아낼 수 있다. 그 다음 알아낸 외부 공기 2차원 벡터를 이용하여 ..

이 문제는 구현, 시뮬레이션 문제이다. 이 문제는 온풍기 바람, 온도 조절을 잘 구현하면 바로 정답이 나온다. 온풍기 바람을 구현하기 위해 bfs를 사용했다. 그러나 ny, nx를 찾는 부분에서 dy, dx 배열을 사용하지 않고 각 케이스를 따로 함수로 만들어서 구현했다. 벽의 유무를 체크하는 부분이 매우 중요했기 때문에 함수로 빼서 구현하였고, 제대로 구현할 수 있었다. 온도 조절 부분은 어항 정리 (23291) 문제와 동일하다. 인접한 모든 부분에 대해 차이에 따라 더하고 빼는 구조인데, 상하좌우를 모두 검사하면 중복으로 체크되는 부분이 있어 오른쪽, 아래만 체크해야 한다. 이중 for문으로 어렵지 않게 구할 수 있다. 구현은 빠르게 했는데 온도 조절 부분에서 y, x를 잘못 써서 계속 정답이 안 나..

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