문제 이해 단계 https://www.acmicpc.net/problem/14502 3개의 벽을 배치하여 얻을 수 바이러스가 퍼지지 않는 방의 최대 개수를 구하는 문제이다. 바이러스는 십자가 모양으로 퍼지고 벽을 통과할 수 없다. 입력으로 연구소의 지도가 주어지고, 출력으로 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하는 문제이다. 이해 자체는 오래 걸리지 않았던 문제이다. 문제 접근 단계 이 문제의 포인트는 무조건 3개의 벽을 활용해야 한다는 점과 입력으로 주어지는 N과 M의 크기가 최대 8로 엄청나게 작다. 게다가 시간제한이 2초, 메모리 제한이 512MB로 넉넉하기 때문에 벽 3개를 전부 다 탐색하는 브루트포스 방식을 사용해도 된다고 생각했다. 그리고 바이러스는 십자가 모양으로 한 칸씩 퍼지는..

문제 이해 단계 https://www.acmicpc.net/problem/18513 문제 이해 자체는 그렇게 어렵지 않은 문제. N개의 샘터와 K개의 집이 주어진다. 이후 샘터의 위치가 지정되고 집의 위치를 지정하는데 집이 샘터에 멀어질수록 불행도가 올라간다. 이때, 불행도의 합을 최소화할 수 있도록 집을 배치한 후, 그때의 합의 최솟값을 구하는 문제이다. 샘터에는 집을 지을 수 없고, 집을 겹쳐지을 수도 없다. 문제 접근 단계 불행도를 최소화하기 위해서는 샘터에 양옆에 차곡차곡 최대한 붙여서 짓는 것이 가장 좋다/ N개의 샘터가 있다면, N개의 샘터를 하나씩 돌아가면서 양쪽에 집을 두면서 진행하는 것이 좋다. 이런 동작원리가 BFS와 흡사하다고 생각하여 BFS로 접근하기로 했다. 1. 모든 샘터들을 큐..

문제 이해 단계 짧아서 이해하기 간단한 문제 N개의 점과 M개의 선이 입력된 후, 그 아래에 연결 노드의 정보들이 입력된다. 그때의 연결 노드의 개수를 구하는 문제이다. 문제 접근 단계 BFS나 DFS로 푸는 대표적인 연습용 문제라서 유추할 필요도 없다. 방향이 없는 그래프이기 때문에 양쪽 모두 연결된다는 점만 기억하면 된다. 예를 들어, 2 5가 입력으로 주어진다면 2 -> 5와 5 -> 2가 동시에 연결되는 것과 동일한 것이다. 나는 이 문제를 벡터와 큐를 이용하여 BFS로 풀었다. 문제 구현 단계 void bfs(int start) { queue q; q.push(start); c[start] = true; while (!q.empty()) { int x = q.front(); q.pop(); fo..

문제 이해 단계 문제 자체는 짧고 이해도 간단한 문제. X축 하나만 존재하고 점 N에서 점 K까지 가는데 총 3가지 방법이 존재한다. 1. 2 * N칸 이동 -> 시간소모 = 0초 2. +1칸 이동 -> 시간소모 = 1초 3. -1칸 이동 -> 시간 소모 = 1초 이 세 가지 방법을 이용하여, 점 N에서 점 K까지 가는 최소 시간을 찾는 문제이다. 문제 접근 단계 처음에는 최소시간을 찾는 것이기 때문에 그리디 문제인 줄 알았다. 하지만 그리디 문제의 조건은 매 순간마다의 최적의 답이 문제의 답이 되어야 한다. 이 문제에서는 나중에 분석한 답이 더 최소 시간 일수도 있기 때문에 그리디로 풀기엔 적합하지 않다. 그래서 x축에서 한 점을 기준으로 양쪽을 탐색하여 K를 찾는 BFS 방식을 사용하기로 했다. 다른..

문제 이해 단계 위 문제는 힌트를 보면 이해하기가 더 쉽다. ....... ...O... ....O.. ....... OO..... OO..... OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOO.OOO OO...OO OOO...O ..OO.OO ...OOOO ...OOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO ....... ...O... ....O.. ....... OO..... OO..... 이를 요약한다면 0초 - 일부 칸 폭탄 설치(초기상태) 1초 - 행동 X 2초 - 폭탄 없는 칸에 전부 폭탄 설치 3초 - 행동 X(0초 때 설치해 뒀던 폭탄 터짐) 이후 2초, 3초 행동 반복 이 말은 폭탄이 터져 그 주..

문제 이해 단계 문제 이해 자체는 크게 어렵지 않다. 얻을 수 있는 돈 p와 날짜 제한인 d가 들어온다. 강연을 하나 할 때마다 1일씩 소모되는데, 이 조건에서 얻을 수 있는 최대 값을 구하는 것이다. 문제 접근 단계 이 문제는 최댓값을 구하는 문제이기 때문에 당연히 얻는 돈이 큰 수를 최대한 뽑는 것이 중요하다. 하지만 시간제한이 존재하기 때문에 같은 시간제한을 가진 강연은 뽑는 것이 제한된다. 예를 들어 (30,1), (20,1)이 있을 경우, 둘 중 하나밖에 고르지 못하는 것이다. 여기선 당연히 (30,1)을 고르는 것이 최선이다. 그래서 나는 이 수들을 내림차순 정렬하여 큰 수를 넣는데, 가능한 조합만 고르려고 하니까 시간초과가 뜰 것 같았다. 그래서 우선순위 큐를 이용하여 값을 넣어주어 제일 작..

문제 이해 단계 문제 이해 자체는 간단하다. N대의 크레인이 있고, 각 크레인마다 무게제한이 존재한다. 이때 박스 K개가 주어지고, 각 크레인마다 하나씩 옮기는 데 걸리는 시간이 1분이다. 이 때, 총 걸리는 시간의 최솟값을 구하는 문제이다. 문제 접근 단계 포인트는 두 가지로 볼 수 있을 것 같다. Point 1. 크레인 무게 제한 각자 들 수 있는 박스를 생각했을 때, 무게 제한이 클수록 들 수 있는 박스가 많아진다. 만약 무게 제한이 5와 3인 크레인이 있다면 3인 크레인은 1,2,3 밖에 못 들지만, 5인 크레인은 1,2,3,4,5까지 들 수 있다. 여기서 중요한 점은 5 크레인은 3 크레인의 박스를 들 수 있지만 그 반대는 안된다는 것이다. 5인 크레인은 3인 크레인에게 영향을 줄 수 있다. 그..

문제 이해 단계 문제 이해가 너무 힘들어서 인터넷을 참고하여 문제를 이해하였다. 한마디로 말하면 집중국은 길이로 나타난다. 만약 1개의 집중국으로 위치가 1,7인 센서를 수신하려면 수신 가능 영역은 6(7-1), 길이 같은 느낌으로 해석하면 된다. 즉, K개의 줄로 각 위치에 있는 센서를 연결하는 최소의 수를 구하는 문제이다. 이해를 위해 예제를 그림으로 알아보면 이런 식으로 나타난다. 2개의 집중국을 사용한 수신 가능 영역의 길이의 최솟값이다. 문제 접근 단계 이 문제는 결국 길이를 최소화하기 위해 K개의 그룹으로 나누는 방법을 따지는 문제이다. 길이는 해당 그룹에서 최댓값 - 최솟값으로 나타난다. 길이를 최소화하기 위해서는 당연히 값이 비슷한 센서를 빼야 한다. 따라서 오름차순 또는 내림차순으로 정렬..