문제 이해 단계 https://www.acmicpc.net/problem/16926 문제 조건만 보면 무슨 소리인지 전혀 모르겠는데 밑에 첨삭된 그림을 보면 어떤 식으로 배열하라는지 바로 알겠다. 그림처럼 가운데를 중심으로 X자 모양으로 2개의 직선과 + 모양으로 2개의 직선을 그리는 것이다. 그리고 가운데를 중심으로 45도를 단위로 돌렸을 때의 결과를 구하는 문제이다. 문제 접근 단계 해당 문제에서 요구하는 것은 배열을 회전시키는 것이다. 회전시켰다는 것을 확인하기 위해 12시 방향에 있던 5가 3시 방향에 위치하는 등, 어떤 그룹의 이동을 통해 확인한다. 여기서 생각이 든 게, 저 배열들을 확실한 그룹으로 나눌 수 없을까? 아래 그림같이 나누면 n이 아무리 늘어나도 같은 방식으로 포함시키면 되기 때문..

문제 이해 단계 집이 원형으로 배치되어 있고, 한 집을 선택하면 양 옆에 있는 집을 선택할 수 없게 된다. 이러한 조건일 때 얻을 수 있는 가장 많은 숫자 합을 고르는 문제 문제는 엄청나게 간단하다. 문제 접근 단계 일단 배치를 신경 쓰지 말고, 그냥 일반적인 문제처럼 일렬로 집이 있다고 생각해 보자. 그러니까 해당 문제에서 원으로 배치된 것을 어떤 집을 기준으로 일렬로 배치한 것이다. 입력을 주어진 그대로 일렬로 배치해 봤다. 구해야 하는 것은 이 중 최적의 집들을 선택해서 최댓값을 구하는 것이다. 3번 집부터 시작한다고 생각하자. 해당 문제에서 집은 최소 3개라고 했으니 3개부터 살펴본다. 그러니까 현재는 왼쪽에 있는 [2,3,4] 집 밖에 없다고 생각하는 것이다. 집 하나를 고르면 양 옆은 고를 수..

문제 이해 단계 입력으로 2차원 맵과, 지나갈 수 없는 장애물(물 웅덩이)이 0~10개 사이로 주어진다. 이때 집과 학교의 위치는 각각 (1,1) (m, n) 위치에 고정이다. 움직일 수 있는 방법은 오른쪽/아래로 움직이는 방법밖에 없을 때, 최단경로로 집에서 학교로 갈 수 있는 경로의 수를 구하는 문제이다. 문제 접근 단계 일단 출발지에서 목적지까지 경로를 구해야 하고, 맵과 장애물이 주어졌다. 높은 확률로 그래프 탐색 문제로 해결하는 것으로 보인다. 일단 움직일 수 있는 조건을 보면 오른쪽과 아래로밖에 이동하지 못한다. 그리고 찾아야 하는 것은 최단경로의 개수이다. 그렇다면 해당 경로가 최단경로인지 아닌지 어떻게 판단할 수 있을까? 사실 판단할 필요 없다. 왜냐하면 오른쪽과 아래로만 움직일 수 있다면..

문제 이해 단계 주어지는 입력은 사용할 수 있는 숫자 N과 만들어야 하는 Number 2개이다. 숫자 N을 통해 할 수 있는 작업은 아래의 2가지 작업 밖에 없다. 1. 사칙연산 2. N을 연속해서 이어 붙이기(ex : 22, 33, 555) 이를 이용해서 Number를 만드는데, 숫자 N을 최대한 적게 사용해야 한다. 이때 숫자 N은 몇 개일까? 만약 8개가 넘는다면 -1을 반환한다. 문제 접근 단계 처음에는 해당 문제가 단순한 사칙연산을 이용한 수학 연산 문제라고 생각했는데, N을 연속해서 이어 붙일 수 있다는 조건에서 단순한 수학 연산은 아닐 것이라는 생각이 들었다. 그래서 일단 N이 1개 일 때부터 만들 수 있는 조합에 대해 적어보기로 했다. N이 1개일 때 N N이 2개일 때 NN, (N+N),..

문제 이해 단계 0과 1로만 이루어진 2개의 서로 다른 2차원 맵이 주어진다. 왼쪽 맵은 0일 때 있는 퍼즐이 있는 것, 오른쪽 맵은 1일 때 퍼즐이 있는 것이다. 왼쪽 맵의 빈칸에 오른쪽 퍼즐을 끼우는데 딱 맞는 퍼즐만 끼울 수 있다. 이때 중요한 것은 퍼즐을 회전해서 끼울 수 있다는 것이다. 이러한 조건일 때 최대한 많은 퍼즐을 끼웠을 때 총퍼즐의 칸 수를 구하는 문제이다. 문제 접근 단계 일단 해당 문제의 유형부터 유추해 보자면 0과 1로만 이루어진 2차원 맵이 주어진 점, 그리고 퍼즐을 알아내야 하는 점을 보면 곧바로 그래프 탐색을 포함한 문제라는 것을 유추할 수 있다. DFS나 DFS 중 하나로 풀면 될 것 같은데 딱히 경로 자체는 그렇게 중요한 점이 아닌 것 같아서, 두 개 중 아무거나 상관없..

문제 이해 단계 알파벳 대문자 3글자로 이루어진 공항(정점)이 존재한다. 그리고 입력으로 티켓(간선) [a, b] 형태로 a->b 로이 단방향 정보로 주어진다. 이때, 모든 항공권을 사용한다는 말은 모든 간선을 사용한다는 말이다. 모든 도시를 방문할 수 없는 경우는 주어지지 않는다는 말은 결국엔 모든 정점을 방문한다는 소리이다. 이때 방문했던 공항 순서대로 출력하도록 하는 게 해당 문제이다. 여기서 한 공항에서 티켓이 여러 개 있다면 사전순(오름차순)으로 더 빠른 것이 우선시된다. 문제 접근 단계 해당 문제는 위에서 말했듯이 공항은 정점이고, 티켓은 두 정점을 잇는 단방향 정보인 간선이다. 그렇기 때문에 해당 문제는 그래프 탐색 문제일 가능성이 높다. 그래서 BFS 또는 DFS로 접근해야 할 것 같은데,..

문제 이해 단계 n개의 섬이 주어지고, 정보로는 각 섬이 이어지는 정보와 그 거리 비용이 주어진다. 이 조건에서 모든 섬을 방문할 수 있도록 선을 이을 때, 돈을 최소한으로 쓰게 하는 문제. 문제 접근 단계 해당 문제는 그림으로만 봐도 알겠지만, 가중치가 주어진 노드 문제이다. "최소한 적은 비용을 골라라" 이 말은 그리디에서 자주 쓰는 말이어서 일단 그리디라고 가정하고 문제를 풀어보겠다. 비용을 최소화하려면 어떻게 해야 유리할까? 1. 비용이 싼 선(다리)을 고른다. 2. 선(다리)을 최대한 적게 쓴다. 2가지 일단 생각난다. 2번 조건이 확실한지 나도 잘 모르겠어서 그림을 여러 번 그려봤다. 왜냐하면 직통으로 가는 다리가 엄청 비싸고, 돌아서 가는 다리가 엄청 싸면 "돌아서 가는 게 더 싼 거 아닌가..

문제 이해 단계 숫자로 이루어진 문자열이 주어지고, 그중에서 없애야 할 문자의 수 k가 주어진다. k개를 지워서 문자열 중 가장 큰 숫자를 만드는 것이다. 여기서 중요한 점은 무조건 k개를 다 써야 한다는 것이다. 문제 접근 단계 상식적으로 한번 접근해 보자. 어떤 문자열(숫자배열)일수록 크다고 할 수 있을까? 당연히 기본적으로 다른 숫자들보다 자릿수가 많으면 비교할 필요도 없이 더 큰 숫자일 것이다. 예를 들어 두 자릿수의 최솟값 (10)은, 한 자릿수의 최댓값(9)보다 무조건 큰 것처럼 말이다. 그럼 비교하는 두 숫자의 자릿수가 같다면? 가장 높은 10의 자리(숫자 배열의 첫 인덱스)가 높은 숫자가 큰 것이다. 예를 들어, "399"와 "400"을 비교하면, 가장 높은 자릿수인 '3'과 '4'만 보고..