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번째 카..

문제 설명 25332번: 수들의 합 8 $A = \{1, 2, 3\}$, $B = \{1, 3, 2\}$로, 조건을 만족하는 $i, j$ 쌍은 $(1, 1), (2, 3), (1, 3)$의 세 가지이다. $A_1$ = $B_1 = 1$ $A_2 + A_3 = B_2 + B_3 = 5$ $A_1 + A_2 + A_3 = B_1 + B_2 + B_3 = 6$ www.acmicpc.net 접근 방법 해당 문제는 원티드 주관 코딩테스트 대회 2022년 2회차의 마지막 문제로서 단순하게 해결할 수 있어 보였지만, 시간 제한 등의 이슈로 다소 깐깐했었던 문제였습니다. 특히, 이 문제의 경우 백준 2015번 문제 '수들의 합 4'과 매우 밀접한 관련이 있는 문제이기에 해당 문제를 풀기 앞서 '수들의 합 4' 문제를 ..