[그리디, 난이도 중] 프로그래머즈, 큰 수 만들기
문자열로 주어진 정수에서 k개의 수를 제거해서 만들 수 있는 가장 큰 수를 계산하는 문제이다. 백준에서 이런 유형의 문제를 풀었던 기억이 있었던 덕에 금방 해결할 수 있었다. 본인의 접근법은 스택의 원리를 이용하는 것이다. 순서대로 정수를 벡터에 넣으며, 기존 벡터의 마지막 인덱스 값(스택 상에선 top)이 현재 push한 정수보다 작을 경우 이 마지막 인덱스 값을 제거해주는 과정을 반복한다. 제거할 때마다 k의 카운트는 1씩 감소시켜야 한다. 해당 규칙으로 입력값의 정수들을 모두 벡터에 넣었음에도 불구하고 수를 k만큼 제거하지 못했을 경우도 있다. 이 과정까지 잘 수행 했다면 벡터의 요소는 ex) (5,4,3,2,1), (7,5,3,2,1), (9,9,7,7,5,5) 같이 내리막수일 것인데, 남은 k가..
2020. 10. 5.
[그리디, 난이도 중] 프로그래머즈, 구명보트
그리디 알고리즘이기 때문에 먼저 people을 오름차순으로 정렬하였다. 본인이 첫 번째로 생각한 접근법은 단순히 체중이 가벼운 순으로 묶는 방법이었다. 50 50 70 80 이 주어졌다면, (50,50),(70),(80) 총 3개의 보트로 테스트 케이스와 일치 50 70 80 이 주어졌다면, (50),(70),(80) 총 3개의 보트 테스트 케이스와 일치 그러나 이 접근법은 5 10 90 95 라는 반례와 막히게 된다. 이 경우에는 내 첫 번째 접근법으로는 답이 3이 나오는데, (5,95),(10,90) 총 2개의 보트로도 가능한 것이다. 정답처리된 본인의 두 번째 접근법은 무게가 가장 가벼운 사람과 가장 무거운 사람끼리 보트에 태우는 것이다. 단, 이 둘의 합이 무게 제한을 넘어갔을 경우에는 무거운 사..
2020. 10. 4.
