1931 - 회의실 배정
처음 시작하는 회의부터 '하나씩' 선택해가면서 어떤 회의를 진행할건지 선택한다고 하자
끝나는 시간이 가장 빠른 회의를 고르면 된다.
가장 먼저 시작할 회의를 '1개' 골랐고, 가장 먼저 끝나는 회의를 골랐기 때문에
회의가 가능한 시간이 제일 많아진다.[
1080 - 행렬
(0, 0)부터 고려해보자
만약 (0, 0)이 A와 B가 다르다면 한가지 경우의 수밖에 없다.
항상 (0,0)을 3x3행렬의 왼쪽상단으로 두고 바꿔야한다.
이제 (0, 1)을 보자 (0, 0)은 이미 A와 B가 같아졌으므로
A와 B가 다르다면 (0, 1)의 3x3행렬의 왼쪽 상단에 두고 변경해야한다.
이제 (0, 2)도 마찬가지다.
즉 (0, 0)을 먼저 고려하게 되면
각 행동의 경우의 수가 1개로 줄어들기 때문에
정답이 될 수 밖에 없다.
1946 - 신입사원
한 요소가 여러 속성으로 이루어져 있고 여러개의 요소를 정렬시켜야 한다면,
어떤 속성 하나를 골라서 정렬한 후 생각하는게 가장 일반적인 풀이다.
또한 나머지 속성들도 어떻게 정렬해야 할지 생각하자.
(이 문제는 한 속성에 관해서만 정렬하면 된다)
이 문제에서는 사원이 서류 심사성적 순위와 면접 성적 순위으로 이루어져 있다.
이제 둘 중 어떤걸로 정렬해도 상관없지만, 서류 심사 성적으로 오름차순 정렬해서 풀자.
서류 심사 성적으로 오름차순 정렬한 순서로, 면접 순서를 관찰하자.
어떤 한 사원은 다른 사원보다 면접순위, 서류순위가 모두 떨어지면 안된다.
그리고 서류성적으로 정렬된 순서로 관찰하기 때문에, 나중에 볼 사원의 서류순위는 먼저 볼 사원보다 떨어진다.
즉 나중에 볼 사원은 앞에서 이미 본 다른 어떤 사원보다도 면접순위에서 우수해야한다.
알고리즘 상으로는 앞에서부터 사원을 보면서 면접순위의 최댓값을 기억하다가,
최댓값보다 작은 사원은 정답에서 제외시키면 된다.
15903 - 카드합체놀이
해당 링크의 파일 합치기3와 같은문제다.
11497 - 통나무 건너뛰기
높은 통나무를 순서로
왼쪽끝, 오른쪽 끝 중 나무 높이 차가 차이가 적은 위치에 위치시킨다.