전체 글 (125) 썸네일형 리스트형 22254 공정 컨설턴트 호석 https://www.acmicpc.net/problem/22254 22254번: 공정 컨설턴트 호석 거듭된 창업 성공을 이룬 류진국 사장은 이번에는 맞춤형 선물을 제작해주는 공장을 만들기로 했다. 현재 들어온 맞춤형 선물 주문은 총 $N$개이며, 각 맞춤형 선물마다 제작에 필요한 시간이 정 www.acmicpc.net 접근 1. X시간 내에 모든 선물을 완성할 수 있는 최소 라인 수를 요구한다. 1부터 N까지 선형탐색으로 찾을 수 있지만, N이 10만이고, X가 10억이기 때문에 시간 초과가 발생할 수 있다. 따라서 log의 복잡도로 줄이기 위해 이분탐색을 사용해야 한다. 2. 최적해를 찾기 위해서는 가장 작은 라인의 공정 시간 + i번째 선물의 공정 시간으로 계산해야 한다. 따라서 우선순위 큐를 사용.. 1938 통나무 옮기기 문제: https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 통나무 옮기는 방향을 상하좌우, 회전 5가지로 구분할 수 있다. 각각의 방향으로 이동한 상태를 기억하기 위해 BFS를 사용하기 적합하다 판단했고, 다음 상태로 이동하기 전에 나무가 있는지, 범위를 벗어나지 않는지를 확인하여 탐색하면 답을 구할 수 있다. 범위를 벗어나는 경우를 좀 더 쉽게 처리하기 위해 기존의 맵을 감싸는 영역을 나무로 저장하도록 했다. import .. 9205 맥주 마시면서 걸어가기 문제: https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 시작 지점부터 근처의 편의점을 들를 수 있다면, 탐색하여 진행하는 과정이 BFS와 유사했고, N의 크기가 100이하로 작기 때문에, BFS로도 충분히 해결할 수 있다고 판단했다. 음수 좌표 값을 간편하게 처리하기 위해서 시작 지점과, 편의점, 도착 지점들을 클래스의 인스턴스로 생성하여 hashmap의 형태로 키에 넣었다. 이후 맨해튼 거리가 1000이하라면 큐에 넣어 탐색하도록 구현했.. 이전 1 ··· 9 10 11 12 13 14 15 ··· 42 다음