코딩테스트 문제 (9) - 효율적인 화폐구성
문제 화폐의 단위가 배열 $a$로 주어지고 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 $m$원이 되도록 하려고 합니다. 각 화폐를 중복해서 사용할 수 있습니다. $m$원을 만들기 위한 최소한의 화폐개수를 구하는 문제입니다. $m$원을 만들 수 없을 때는 -1을 return합니다. 1. a = [2,3], m = 15 => 5 2. a = [3], m = 4 => -1 풀이 1번 문제부터 생각해보겠습니다. 15를 만드는 경우의 수는 [2,2,2,3,3,3], [3,3,3,3,3],[2,2,2,2,2,2,3] 의 3가지가 있는데 이중 [3,3,3,3,3]이 개수가 제일 적어 답은 5가 됩니다. 먼저, 화폐단위보다 작은 $m$은 조합을 만들 수 없기 때문에 -1을 return합니다. $m$을 만들..
코딩테스트 문제 (8) - 개미 전사
문제 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 침입합니다. 식량창고는 정해진 수의 식량을 저장하고 있고 일직선으로 나열되어 있습니다. 메뚜기 정찰병은 인접한 식량창고가 공격받으면 바로 알아차릴 수 있습니다. 따라서, 개미 전사가 정찰병에게 들키지 않고 식량창고를 털기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 공격해야 합니다. 식량창고가 배열로 주어졌을 때, 개미 전사가 약탈할 수 있는 최대 식량을 구하는 문제입니다. 1. [1,3,1,5] => 8 2. [1,2,3,1] => 4 3. [2,7,9,3,1] => 12 풀이 1번 케이스의 [1,3,1,5]를 생각해보면, 개미가 첫 번째 인덱스를 (1) 약탈한다면 세 번째 인덱스 (1) 이나 네 번째 인덱스밖에 (5) 약탈할 수 없..
