[백준 / 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] 17780 새로운 게임 (Java)
문제 출처 : https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net (...) 풀이 문제에서 주어진 그대로 풀면되는 시뮬레이션 문제였다. 문제 해석시 주의할점이 있었는데, 1. 다음 위치가 빨간색인데, 이동할 위치에 이미 다른 체스말들이 있는경우, 이동후 체스말을 위로 쌓은다음에 체스말의 순서를 뒤집는것이 아니라, 이동 전에 뒤집고 체스말을 위로 쌓는것이다. 예를들어, 현재 이동할 체스말들이 (1,2,3) 순서대로 쌓여있고 이동위치에 이미 (4,5)..
