Ikjo's Technology blog

문제 설명 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 접근 방법 5개월 전 체스판 다시 칠하기(백준 - 1018) 라는 문제를 푼 적이 있었는데, 최근 체스판 다시 칠하기 2(백준 - 25682) 문제가 새롭게 등장했습니다. [백준 - 1018] 체스판 다시 칠하기 - Java 문제 설명 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검 ikjo.tistory.com 앞서 풀었던 체스판 다시 칠하기..

문제 설명 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 접근 방법 해당 문제는 너비 우선 탐색을 이용하여 해결할 수 있었습니다. 2차원 그래프상 특정 지점들간 최단 거리는 보통 너비 우선 탐색을 적용하는데, 깊이 우선 탐색의 경우 말그대로 깊이 탐색하기 때문에 해당 경로가 '최단' 경로인지 구분하기가 어려움 점이 있습니다. 일단 벽을 부수는 것을 제외하면 일반적인 너비 우선 탐색 문제입니다. 벽을 하나 부숴야 함으로써 난이도가 꽤나 상승했습니다. 벽을 하나 부숴야 하기 때문에 특정..

문제 설명 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 접근 방법 해당 문제는 이분 탐색을 이용하여 해결할 수 있었습니다. 여기서 이분 탐색을 찾고자 하는 것은 가장 인접한 두 공유기 사이의 최대 거리입니다. 이때 이분 탐색을 위한 시작점(start)을 1로 두었는데, 이는 인접한 두 공유기 간의 거리가 최소일 경우이기 때문입니다. 또한 끝점(end)을 첫번째 집과 마지막 집 사이의 거리(좌표 차)로 두었는데, 이는 인접한 두 공유기 간의 거리가 최대일 ..

문제 설명 20159번: 동작 그만. 밑장 빼기냐? 카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다. 둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다. www.acmicpc.net 접근 방법 우선 문제에서 주어진 예시를 기준으로, 정훈이가 얻을 수 있는 카드 값의 합의 경우의 수는 다음과 같습니다. 이때, 각 경우의 수를 '밑장을 빼서 자신한테 분배한 경우'와 '밑장을 빼서 상대한테 분배한 경우'로 나누어 생각해볼 수 있겠습니다. 우선 밑장을 빼서 자신한테 분배한 경우를 살펴보겠습니다. 이 경우 당연히 정훈이의 카드 패에는 밑장(카드 패 맨 마지막 순서)이 항상 포함됩니다. 그리고 1번째 및 3번째 카드와 2번째 4번째 카..

문제 설명 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 접근 방법 해당 문제에서는 중위 순회 결과와 후위 순회 결과가 주어졌을 때 이를 통해 전위 순회 결과를 요구하고 있습니다. 이를 위해선 중위 순회 결과와 후위 순회의 결과로 트리를 재현하는 것이 우선입니다. (참고로 '전위 순회 결과와 중위 순회의 결과' 그리고 '중위 순회 결과와 후위 순회 결과'로는 트리를 재현할 수 있지만, '전위 순회의 결과와 후위 순회의 결과'로는 트리를 재현할 수 없습니다.) 우선 이 문제에 접근하기 앞서 중위 순회와 후위 순회의 특성에 대해 알아야합..