재원블로그 재원블로그

이 문제는 구현 문제이다. 규칙성을 찾아내는 것이 가장 중요한 포인트이다. N이 주어졌을 때 가로의 길이는 N번째 홀수와 같다. 따라서 2 * N - 1이 된다. 또한 높이가 주어졌을 때 높이 / 2 한 부분에서 2개의 삼각형이 나오게 된다. 또한 각 2개의 삼각형의 x좌표는 각각 x - height / 2, x + height / 2가 된다. 이러한 규칙성을 찾았다면 재귀를 통해 구현하고, 높이가 3일 때를 base case로 잡아 문제를 해결할 수 있다. #include #include #include using namespace std; vector output; void draw(int y, int x, int height) { if (height == 3) { output[y][x] = '*';..

이 문제는 다이나믹 프로그래밍 문제이다. 이 문제는 LIS 문제를 두 번 쓴 다음에 합치면 되는 간단한 문제이다. dp1[i] : i를 마지막으로 하는 가장 긴 증가하는 부분 수열 (왼쪽 기준) dp2[i] : i를 마지막으로 하는 가장 긴 감소하는 부분 수열 (오른쪽 기준) 으로 세우고 마지막에 각 인덱스 i에 대해 이를 합친 결과 중 가장 긴 것을 답으로 내면 정답이 나온다. #include #include using namespace std; #define MAX 1000 int N; int arr[MAX]; int dp1[MAX]; int dp2[MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; f..

이 문제는 분할 정복을 이용해서 푸는 문제이다. 문제가 아주 어려운 얘기로 가득한데, 결론적으로 S1/N1 + S2/N2 + ... + SM/NM 을 구해야 하고, 여기서 곱셈 역원을 계산할 때 b^(x - 2) (mod X) 를 사용하라는 얘기이다. 따라서 이 문제는 분할 정복을 사용하여 거듭제곱을 풀 수 있으면 된다. 값이 매우 크기 때문에 모듈러 연산을 곳곳에 배치해두었다. 중요한 점은 마지막 answer에도 모듈러 연산을 해줘야 정답이 나온다는 것이다. #include #include #include #include #include using namespace std; #define MOD 1000000007 typedef long long LL; LL calculate(LL a, LL x) { ..

이 문제는 다익스트라 알고리즘을 사용해서 풀었다. 이 문제는 얼핏 보면 그냥 dfs와 같은 방식으로 풀릴 것 같지만, 그렇지 않다. 어떤 점에서 다른 점으로 가는 방식이 여러가지라면, 그 중에 가장 cost가 적게 드는 방법으로 가야 한다. 이를 위해 다익스트라 알고리즘을 사용해서 nextCost가 m보다 작거나 같을 때까지 실행한다. 이 때 주의할 점은 다익스트라 알고리즘을 돌리는 와중에 아이템 개수를 추가하면 오답이 나온다. 이는 다익스트라 알고리즘 특성상 이미 방문했더라도 더 짧으면 다시 방문할 수도 있기 때문이다. 따라서 다익스트라 알고리즘을 다 돌린 뒤에 INF가 아닌 점들의 개수를 더해주면 정답이 나온다. #include #include #include #include #include usin..

이 문제는 시뮬레이션 문제로, 구현이 매우 어려운 문제였다. 중간에 풀다가 안 풀려서 구글링을 했지만 bfs를 이용한 풀이가 많았고, 이는 내가 처음에 구현한 것과 접근 방식이 너무 달라 적용하지 못했다. 결국 다시 반례들을 적용하면서 천천히 디버깅했고, 문제를 발견하여 해결할 수 있었다. 내 풀이의 핵심은 RED를 먼저 굴리고, BLUE를 그 다음, RED 한번 더, BLUE 한번 더 이다. 여기서 시간 초과가 나지 않으려면 위 과정을 거쳐도 두 구슬 모두 제자리에 있으면 바로 continue를 해버리는 것이다. 그렇지 않으면 가만히 있는 모든 케이스를 탐색하므로 시간 초과가 발생한다. 내가 놓쳤던 부분은 첫번째로 RED와 BLUE를 탐색하고, 한번 더 탐색하는 부분이었는데, 이 때 매개변수로 받은 r..

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 입력 배열의 최대 크기가 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를 잘못 써서 계속 정답이 안 나..