[백준 / BOJ] 11509 풍선 맞추기
문제 출처 : https://www.acmicpc.net/problem/11509 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 높이가 같거나 다른 N개의 풍선이 직선에 있다. 화살을 날려 풍선을 터트릴 수 있는데, 한 풍선을 터트릴때마다 화살의 높이가 1만큼 낮아진다. 이때, 모든 풍선을 터트리기위해 필요한 화살의 최소횟수를 구하는 문제다. 풀이 아이디어?로 풀리는 문제였다. 풍선이 최대 1,000,000개 주어지기 때문에, 완전탐색으로는 풀 수 없다. 문제를 풀기위해, 이전에 던져진 화살들의 위치를 기억하는 방식으로 풀었는데, 이러면 O(N)시간복잡도로 문제..
[백준 / BOJ] 14442 벽 부수고 이동하기 2 (Java)
문제 출처 : https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net N*M크기의 맵이 있고, 이 맵은 벽과 땅으로 이루어져있다. 벽을 부술수있는 횟수 K가 주어질때, K번 이하로 벽을 부수면서 (N,K)지점에 도착하는 최소 거리를 구하는 문제다. 풀이 BFS에 3차원 체크배열로 재방문을 잡아내며푸는 문제였다. 체크배열을 3차원으로 지정해야하는 이유는, (y,x)지점에 도달했을때, 벽을 A+1번 부순횟수보다 A번 부..
