재원블로그 재원블로그

이 문제는 시뮬레이션 문제이고, bfs를 활용하여 풀었다. 이 문제에서 가장 어려운 부분은 첫 번째로 블록 그룹을 찾아내는 것이고, 두 번째는 중력 작용을 시키는 것이다. 첫 번째는 bfs를 이용하였는데, node라는 구조체를 만들어 필요한 정보들을 넣도록 하였고, 이를 bfs에서 리턴하도록 했다. 주의할 점은 격자에서 무지개 블록, 즉 0은 visited에 포함되면 안된다. 그러나 bfs 내부에서 0에 대한 visited를 처리하지 않으면 당연히 무한 루프에 걸리게 된다. 이를 해결하기 위해서 일단 bfs를 수행하고, bfs가 끝난 뒤 무지개 블록에 대해 visited가 true가 되어있는 걸 false로 바꿔주면 된다. 상하좌우가 중요하지 않다는 점도 중요한 포인트이다. 임의의 (y, x)에 대해 같..

이 문제는 bfs를 이용해서 풀었다. 이 문제에서 핵심은 택시가 손님들을 찾는 과정에서 최단거리이며, 만약 거리가 같은 경우 행 번호가 작은, 행 번호도 같다면 열 번호가 작은 손님을 찾는 것이다. 이를 위해 처음에는 bfs의 상하좌우 탐색 순서를 상좌우하 순서로 탐색하고 찾은 경우를 리턴했지만, 이는 정답이 나오지 않았다. 그래서 두 번째 방법으로 일단 bfs를 맵 전체에 대해 돌리고, 손님들의 startY, startX를 기준으로 오름차순 정렬한 배열에 대해 최단거리를 비교하며 손님을 뽑는 형식으로 바꿔 정답을 도출해낼 수 있었다. 이 부분만 잘 해결한다면 나머지는 쉽게 구현 가능한 문제였다. #include #include #include #include #include using namespace..

이 문제는 시뮬레이션 문제이다. 일단 main에 있는 for문이 1,000번 돌아가므로, for 문 안의 연산의 수가 약 100,000 이면 1초 안에 풀 수 있다. 물론 실제로는 입력 받기, 전처리 등이 for문 전에 있으므로 약 50,000번 정도의 알고리즘이면 안전하다고 생각했다. 이 문제는 냄새 배열과 상어 배열을 따로 만드는 것이 훨씬 구현을 간단히 할 수 있다. 또한 각 상어의 우선순위 방향을 입력받을 때 -1을 해서 받으면 더 용이하게 구현할 수 있다. 한 가지 주의할 점은 각 초마다 냄새를 -1을 해야하는데, 이를 먼저 하고 상어를 움직이면 상어 움직임이 정답과 다른 방향으로 가게 된다. 상어를 움직이고 난 뒤 냄새를 -1하고, 상어가 있는 위치의 냄새를 다시 초기화하면 정답이 나온다. /..

이 문제는 시뮬레이션 문제이다. 입력 N이 최대 10,000 이므로 각 루프마다 10,000번 이하의 연산 수를 가지면 1초 안에 풀 수 있다. 이 문제를 풀 때 중요한 포인트는 블록을 처음에 파란 부분과 초록 부분으로 옮길 때 어떻게 옮기는 지와 블록 한 줄이 사라졌을 때 어떻게 끝으로 밀지이다. 첫 번째 포인트에서는 move 함수를 정의하여 한 점에 대해 위치할 수 있는 좌표를 리턴한다. 이를 통해 2 x 1에서 파란 부분일 때나 1 x 2에서 초록 부분일 때를 해결할 수 있다. 두 경우 한 점씩 리턴받은 값을 비교하여 좀 더 빨간 부분에 가까운 쪽으로 좌표를 정하도록 하면 무리없이 구할 수 있다. 두 번째 포인트에서는 살짝 어려웠는데, 처음에 blue, green 전역 배열을 vector가 아닌 2..

이 문제는 그리디를 이용해서 푸는 문제이다. 매 테스트 케이스마다 최대 100000만의 입력이 주어지므로, O(n) 이하의 알고리즘으로 풀어내야 한다. 즉, O(n^2) 알고리즘으로는 절대 풀 수 없다. 그래서 그리디를 떠올렸고, 처음에는 서류 기준으로 정렬해서 최고의 점수를 낸 사람의 두 점수를 기준으로 한번 거르고, 그 다음에는 면접 기준으로 걸러서 정답을 제출했는데 틀렸다. 결국 도저히 안 풀려서 검색을 통해 도움을 받았다. 내가 간과한 것은 최고의 점수를 낸 사람의 기준으로만 탐색을 돌렸다는 것이다. 그럴 필요 없이 한 가지에 대해 정렬하면 일단 그 기준에 대해서는 첫번째 인덱스를 제외하고는 전부 탈락 위기라는 것이다. 이 때 다른 한 가지 기준을 만족하는지 보고, 만족할 경우 그 값으로 최고 점..

이 문제는 그리디 문제이다. 나는 배수 판정법이라는 것을 모르는 상태로 이 문제를 풀었다. 일단 30의 배수가 되려면 10의 배수가 되어야 하므로 0의 개수가 0개이면 -1을 출력했다. 그 다음 여러 숫자들을 보며 규칙성을 찾았는데, 자릿수마다의 수를 모두 더한 수가 3으로 나누어떨어지면 3의 배수가 된다는 사실을 찾았다. 그래서 반신반의한 마음으로 제출했는데 맞았다. 30의 배수 중 가장 큰 수를 출력하라고 했기 때문에 입력 스트링을 내림차순으로 정렬하면 당연히 제일 큰수가 나올 것이므로 그렇게 풀었다. #include #include #include using namespace std; int main() { string input; cin >> input; bool flag = false; for ..

이 문제는 그리디를 이용해서 푸는 문제이다. 내가 생각한 방법은 현재 위치의 cost와 다음 위치들의 cost들을 비교하고, 만약 현재 cost보다 크거나 같으면 넘어가고, 작은 cost가 나올때까지 간다음, 현재 위치에서 그만큼의 연료를 충전하고 해당 위치로 이동하는 것이었다. 그러나 구현 실수로 정답이 나오지 않았는데, 이는 for문을 돌리다가 현재 cost보다 작은 cost가 나오면 바로 break를 해버려 해당 위치까지 이동하는 계산이 빠졌기 때문이다. 다시 구현하니 바로 정답이 나왔다. 한 가지 주의할 점은 만약 while (true) 로 하고 if (index == N - 1) break; 이런식으로 구현하면 무한 루프에 돌아가게 되는데, 이는 만약 for문이 break로 끝나지 않고 끝까지 ..

이 문제는 그리디를 이용해서 푸는 문제이다. 병렬로 사용했을 때 한 로프에 걸리는 중량은 w/k 이다. 최대 중량은 로프 중 가장 작은 로프에 걸리는 중량의 최대이다. 따라서 (로프 중 최소 중량) = w / k 이고, w = (로프 중 최소 중량) * k 가 된다. 따라서 로프들을 내림차순으로 정렬한 뒤, 최대를 갱신해가며 루프를 돌리면 정답이 나온다. #include #include #include using namespace std; int main() { int N; vector rope; cin >> N; for (int i = 0; i > maxWeight; rope.push_back(maxWeight); } sort(rope.begin..