골드2 에 해당하는 그리디 문제이다. 백준은 신기하게도 문제가 롤 처럼 티어로 나뉘는데 골드2면은 그래도 어려운 편에 속하는 문제라고 볼수있을거같다. 문제 예제는 쉽고 문제 자체도 이해하는데 어렵지는 않다. N 이라는 플러그가 있고 전기 용품의 총 사용횟수인 K 가 주어질때 플러그를 가장 적은 숫자를 뺀 횟수를 리턴하면 된다.
플러그는 N 만큼의 전기용품을 넣을 수 있기때문에 최대한 적은 숫자의 플러그를 빼기 위해서는 꽤 많은 생각이 필요했다.
첫번째로, 만약 지금 플러그에 빈 공간이 있을경우 그냥 순서대로 그대로 집어 넣어주면 된다. 두번째, 만약에 순서대로 전자용품을 사용하고 있는데 이미 꽂혀져있는 플러그라면 그대로 다음 용품으로 넘어간다. 그러나, 만약에 모든 플러그가 꽂혀있는 상태로 새로운 플러그를 보게된다면 이제 어느것을 먼저 뽑을지를 고민해야한다.
내가 생각했던 아이디어는, 뽑는 선택을 남은 횟수로 선택하자 였다. 예를 들어, 첫번째 예시에서 구멍이 3개인 플러그에
키보드, 헤어드라이기, 핸드폰 충전기가 있을때. 키보드와 헤어드라이기 와는 달리 핸드폰 충전기는 더 이상 안쓸거기 때문에 없애고 디지털 카메라 충전기를 넣는거다.
이처럼 "횟수" 를 기반으로 풀었던 첫번째 시도는 그냥 틀렸다. 백준은 그리고 너무 정 없이 뭐가 틀린지 나오지도 않고 그냥 틀렸다고만 얘기해서 좀 서운한거같다.
2 15
3 2 1 2 1 2 1 2 1 3 3 3 3 3 3
찾아본 결과, 이런 테스트 케이스 같은 경우에는 횟수로만 따지면 2를 처음에는 없애는게 맞는데 그렇게되면 총 7번이나 플러그를 빼야한다. 그리고 여기서 배울수 있는점은 "횟수"를 고려할경우에는 앞으로 더 이상 쓰이지 않을 용품을 빼는게 맞고, 그게 아니라면 가장 마지막에 쓰이는 전자용품을 빼는게 맞는것이었다.
출처: https://fisher10001.tistory.com/116
내 코드랑 비슷한데 찾아보던중 훨씬 깔끔하게 써서 한번 옮겨적었다. 그리디 문제는 아이디어 구상까지가 중요한데 내가 좀 복잡하게 생각했던것도 있었고 문제 자체가 난이도가 있는 문제로 출제되다보니 나도 많이 말렸던거같다. 결국에는 맞았지만 정말 찝찝했고 앞으로도 더 풀어야겠다는 생각이 든다
배운점:
1. 문제를 그냥 많이 풀어보자
2. 생각을 정확하게 해보자
