11000 - 강의실 배정
1374 - 강의실
19598 - 최소 회의실 개수
1689 - 겹치는 선분
Ti < Sj 인 수업이 있을경우, 교실을 재사용할 수록 강의실 개수는 적어짐.
2212 - 센서
13164 - 행복 유치원
선분의 일부를 잘라내, 남은 모든 길이의 합을 최소로 하려한다.
이때, 잘라내는 선분들의 길이가 길 수록 남은 길이의 합은 항상 작아진다.
12904 - A와 B
12931 - 두 배 더하기
A에서 할 수 있는 행동은 2가지지만
B에서 가능한 행동을 1가지 뿐이다
그래프를 떠올리면 직관적인 문제상황이 보인다.
1092 - 배
무게제한이 20, 10인 크레인이 있다고하고, 무게가 15, 19인 박스가 있다고하자,
20인 크레인이 15인 박스를 옮기면 10인 크레인은 19인 박스를 옮길 수 없으므로
2분의 시간이 소요된다.
때문에 무거운 크레인부터 자신이 옮길 수 있는 박스 중 가장 무거운 박스를 선택해 옮겨야한다.
1461- 도서관
두개의 소재가 들어간 문제이다.
두 소재 모두 그리디다.
첫번째 소재는 밑에 있는 11508 문제를 먼저 풀면 이해가 갈 것이다.
우선 양수의 책들, 음수의 책들을 나눈 후 최대한 절댓값이 큰 수들부터 M개씩 묶어주면 된다.
두번째 소재는 각 묶음들을 가고, 오는 걸음 수를 따져야 하기 때문에 두 배를 곱해야하는데,
그 중 한 묶음을 가져다 놓고 다시 오지 않아도 되기 때문에 두 배를 곱할 필요가없다.
즉 한 묶음을 1/2배 할 수 있다는 뜻인데, 가장 큰 묶음을 1/2배 해줘야 걸음 수의 합이 작아짐은 당연하다.
11508 - 2+1 세일
2138 - 전구와 스위치
순환되는 경우 한 지점을 기준으로 CASE를 나누고 관찰한다.
21758 - 꿀 따기
if 꿀이 맨 왼쪽 또는 오른쪽에 있는 경우
벌 중 하나는 항상 꿀의 반대쪽 끝에 있어야 항상 제일 많은 꿀을 먹을 수 있음.
나머지 벌 중 하나는 모든 인덱스를 고려해 최대일때를 찾는다. O(N)
else (꿀이 맨 왼쪽과 오른쪽을 제외한 나머지 위치 중 하나에 있는경우)
벌 들은 각각 양쪽 끝에 있어야 가장 많은 꿀을 먹음
꿀의 위치는 모든 인덱스를 고려해 찾는다 O(N)
19539 - 사과나무
-
모든 높이의 합은 3의 배수가 되어야한다.
-
3을 X번 뿌렸다면, 2를 X번 뿌릴 수 있을 때, 1을 X번 뿌릴 수 있음은 자명하다.
19940 - 피자 오븐
경계값이 중요하다. 35와 5를 기준으로 생각하자
BFS로도 풀어보자
7983 - 내일 할거야
6068 - 시간 관리하기
시험본다고 생각해보자, 공부해야할 일 수와 끝날은 정해져 있으므로
최대한 늦게하면 공부를 하기 전까지 제일 많이 놀 수 있다.
16678 - 모독
자연수인 공차가 1이하가 되도록 하는 수열을 만드는 가장 적은 해커 수를 찾는다.
17828 - 문자열 화폐
각 알파벳의 ASCII가 앞에서부터 작아야한다.
23559 - 밥
항상 밥을 먹어야하므로, 처음에는 아무런 제약이 없는 1000원밥을 계속 먹는다고 가정한다.
후에 돈이 되는데까지 더 많은 맛의 이득을 볼 수 있는 5000원 밥으로 변경시켜주면 된다.