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차원 그래프상 특정 지점들간 최단 거리는 보통 너비 우선 탐색을 적용하는데, 깊이 우선 탐색의 경우 말그대로 깊이 탐색하기 때문에 해당 경로가 '최단' 경로인지 구분하기가 어려움 점이 있습니다. 일단 벽을 부수는 것을 제외하면 일반적인 너비 우선 탐색 문제입니다. 벽을 하나 부숴야 함으로써 난이도가 꽤나 상승했습니다. 벽을 하나 부숴야 하기 때문에 특정..

문제 설명 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' 문제를 ..

문제 설명 25331번: Drop 7 Drop7은 7×7 크기의 격자에서 진행하는 싱글 플레이어 게임이다. 처음에는 격자가 비어있고, 플레이어는 매 턴마다 1 이상 7 이하의 정수 하나가 적힌 공을 받아 7개의 열 중 한 곳에 떨어뜨려야 한 www.acmicpc.net 접근 방법 해당 문제는 원티드 주관 코딩테스트 대회 2022년 2회차 문제로서 당시 시간적 여유가 있었음에도 불구하고 문제 해결을 위한 아이디어가 떠오르지 않아 제대로 접근조차 하지 못했었던 문제였습니다. 그래서 아쉬운 마음에 코딩테스트 이후에 따로 시간을 내서 재도전 해보았습니다. 우선 문제를 해결하기 위해 접근했었던 방법을 단계별로 나타내면 다음과 같습니다. 1. 각 열별로 공 떨어트리기 - 떨어뜨린 공은 이미 배치되어 있는 공 바로 ..

문제 설명 25330번: SHOW ME THE DUNGEON 올 여름 출시된 RPG 게임 "SHOW ME THE DUNGEON"은 주인공 시루가 몬스터에게 침략당한 마을을 구하는 내용의 게임이다. 배경이 되는 나라는 $0, 1, 2, \cdots, N$번의 번호가 붙어있는 $N+1$개의 마을로 이루 www.acmicpc.net 접근 방법 해당 문제에서는 캐릭터(시루)의 체력과 마을별 몬스터의 공격력과 주민의 수가 주어졌을 때 시루가 해방시킬 수 있는 주민들의 최대 수를 요구하고 있습니다. 접근 방법 1 : 순열 - 시간 초과 처음 이 문제에 접근했었던 방식은 시루가 각각의 던전들을 순서를 고려하면서 방문하는 모든 경우의 수(순열)를 구함으로써 해방시킬 수 있는 주민들의 최대 수를 구하는 것이었습니다. (..