[이코테] 그리디_만들 수 없는 금액(파이썬/자바스크립트)

이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고

---

문제

---

정답 코드

나의 풀이

 

 

풀이 1

파이썬 Ver.

 

 

자바스크립트 Ver.

 

 

---

문제 풀이

 문제 해설부터 말하자면 입력값을 오름차순으로 먼저 정렬한다. 그 다음 입력값이 작은 것부터 확인하며 현재 확인하는 값으로 target 금액을 만들 수 있는지 확인한다. 즉 현재 확인하는 값이  target 금액 이하인지만 판별하면 되는 문제이다.

 우선 for 반복문으로 주어진 숫자를 탐색하며 현재 탐색하는 숫자 num이 target보다 작지 않다면 해당 값을 target에 누적한다. 이렇게 누적된 수는 누적된 수 이하의 수는 주어진 숫자를 활용하여 모두 만들 수 있다는 뜻이다. 주어진 숫자가 [1, 2, 3]일 경우 조합할 수 있는 숫자는 다음과 같다.

 주어진 숫자 [1, 2, 3]으로는 6 이하의 숫자는 모두 조합할 수 있지만 6보다 큰 숫자는 조합하지 못한다. 따라서 이 경우 정답은 7이 된다. 주어진 숫자가 [1, 2, 3, 8]인 경우를 자세히 한 번 더 살펴보자.

 나는 이 문제를 다른 방법으로 풀었다. 우선 오름차순으로 주어진 숫자를 정렬하고 이중 for문을 활용해 정답을 도출했다. 바깥 for문을 주어진 숫자 중 가장 큰 수 만큼 반복하는데 이때 주어진 숫자가 1이라면 즉시 2를 반환한다. 2가 아니라면 변수 tmp에 i를 담고 주어진 숫자를 한 번 더 j 반복문으로 돌면서 tmp에서 j를 빼나간다. 이때 j반복문을 마친 뒤 tmp가 0이 아니라면 해당 tmp를 반환한다. 어떤 숫자를 주어진 숫자를 활용해 0을 만들 수 없다는 것은 주어진 숫자를 조합해서 해당 숫자를 만들 수 없다는 뜻과 같기 때문에 이렇게 풀었다.