본문 바로가기

알고리즘 문제풀이/백준134

[백준 15810] 풍선 공장 www.acmicpc.net/problem/15810 15810번: 풍선 공장 1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 www.acmicpc.net 이분탐색을 사용하여 조건에 맞는 최솟값을 리턴하는 문제이다. 최소 시간을 리턴해야하므로 b=m이어도 end를 최대한 줄여야 한다. b< m인 경우 mid가 조건에 만족하지 않는, 즉 정답값이 아니므로 start는 mid+1에서 시작한다. 마지막에 리턴하는 값은 end값으로 end연산할때마다 최솟값을 업데이트하는 방법으로 계산해도 된다. ++ 추가코드 long long a =.. 2020. 12. 28.
[백준 17451] 평행 우주 www.acmicpc.net/problem/17451 17451번: 평행 우주 행성 1에 가기 위해 필요한 것보다 세 배의 속도로, 행성 2의 경우 두 배의 속도로 이동하면, 지구에서는 900의 속도만 쌓으면 된다. www.acmicpc.net 카테고리가 이분탐색이긴 한데 잘 모르겠다.. 풀이 방법은 뒤에서 부터 순회하며 값을 찾는다. 현재의 값의 배수면서 && 이전 값보다 큰 최솟값을 찾는다. #include using namespace std; int n; int arr[300001]; int main(void) { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } long long res = arr[n - 1]; for (.. 2020. 12. 27.
[백준 16918] 봄버맨 www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 뭔가 쉬운데 헷갈렸던 문제.. bfs가 살짝 필요한 구현문제이다. 3초짜리폭탄을 설치하고 1초를 냅둔다. 2초에 빈자리에 폭탄을 설치한다. 폭탄이 0초가 되면 터지고 주변에 폭탄이 있다면 같이 터진다. 그뒤로 폭탄 설치와 폭발이 반복이다 폭탄 설치는 짝수 초에 계속된다. 그래서 남은 폭탄 시간을 저장하는 이차원 배열 time을 만들었다. 폭탄 설치 시 3이 저장되며 폭탄이 없는 공간은 -1이다. 배열이 0이 되면 폭탄이 터져서 .. 2020. 12. 27.
[백준 16235] 나무 재테크 www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 어렵진 않았는데 조건이 너무 복잡했던 문제.. 봄+여름/ 가을/ 겨울로 나눠준다. 가을 겨울은 상대적으로 쉬우니까 패스 봄이랑 여름이 같이 구현되는게 편하다. 이 때 주의할 점은 1. 봄에 양분을 먹고 나이가 증가한다는 점 2. 죽은 나무가 주는 양분은 나무가 전부 죽은 후 생긴다는 점: 여름에 죽은 나무가 양분이 되기 때문 이 두 가지를 체크해야 한다. #include #include #inc.. 2020. 12. 26.

티스토리툴바