기맹기 개발 블로그

BOJ 12869 뮤탈리스크 난이도 : 골드 4 https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 전략 처음에는 hp가 많이 남은 순으로 9, 3, 1을 배정해서 그리디로 풀 수 있을까 고민했다. 하지만 12, 9, 3 같은 경우를 생각해보면 12, 9, 3 -> 3, 6, 2 -> 0, 0, 1 -> 0, 0, 0 으로 3번이 되는데 최적의 방법은 12, 9, 3 -> 9, 0, 2 -> 0, 0, 0 으로 2번만에 가능한 것을 볼수 있다. 즉 경우의 ..

BOJ 1987 알파벳 난이도 : 골드 4 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 전략 주어진 조건을 만족하도록 DFS로 탐색하면서 가장 많이 이동한 칸을 저장하면 된다. 시행착오 간단한 문제로 시행착오는 없었다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { stati..

BOJ 2239 스도쿠 난이도 : 골드 4 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 전략 간단한 백트래킹 문제로 예전에 c++로 한번 풀었던 적이 있다. (BOJ 2580) 재귀에 너무 익숙해져있는 것 같아서 이번에는 스택으로 구현해보고자 풀어보았다. 시행착오 재귀로는 정적 배열을 수정하면서 간단하게 백트래킹을 구현할 수 있었다. 스택으로 하려니까 실패했을 때 이전 상태로 돌리는 것을 어떻게 처리할지 고민을 많이 했다. 따라서 cl..

BOJ 17472 다리 만들기 2 난이도 : 골드 1 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 전략 문제를 보고 처음 생각한 전략은 1. dfs로 섬 구분 2. bfs로 섬 간의 최소 거리를 가지는 간선 만들기 3. 크루스칼로 MST 만들기 그래프 종합 선물세트 같은 느낌이다! 그런데 다리를 이을 때 가로/세로 방향으로 일자로만 가능하며 방향을 중간에 바꿀 수 없다는 제약이 있어서 bfs 안쓰고 간선을 만드는 과정을..