Harry Potter

출처 : http://codingdojo.org/cgi-bin/index.pl?KataPotter

해리포터 시리즈가 시중에 1~5권 까지 나와 있다고 한다. (현재는 더 많은 시리즈가 있긴 하지만..)

책 한권의 가격은 8 EUR 이다.

하지만 다음과 같은 조건으로 책 값을 할인 받을 수 있다고 한다.

  • 서로 다른 두 권을 구입하면 5% 할인
  • 서로 다른 세 권을 구입하면 10% 할인
  • 서로 다른 네 권을 구입하면 20% 할인
  • 서로 다른 다섯 권(전부!)을 구입하면 25% 할인

여러분은 이제 저마다 쇼핑카트에 가득 해리포터 책들을 담고 있는 손님들을 위해 가장 적은 금액으로 책들을 구입할 수 있도록 도와주는 알고리즘을 작성해야 한다.

예를 들어 다음과 같이 책을 구입한다면

  • 2 copies of the first book
  • 2 copies of the second book
  • 2 copies of the third book
  • 1 copy of the fourth book
  • 1 copy of the fifth book

여러분이 작성한 알고리즘을 이용하면 51.20 EUR 이라는 최저가가 나와야 한다.


테스트 케이스

def test_basics
  assert_equal(0, price([]))
  assert_equal(8, price([0]))
  assert_equal(8, price([1]))
  assert_equal(8, price([2]))
  assert_equal(8, price([3]))
  assert_equal(8, price([4]))
  assert_equal(8 * 2, price([0, 0]))
  assert_equal(8 * 3, price([1, 1, 1]))
end

def test_simple_discounts
  assert_equal(8 * 2 * 0.95, price([0, 1]))
  assert_equal(8 * 3 * 0.9, price([0, 2, 4]))
  assert_equal(8 * 4 * 0.8, price([0, 1, 2, 4]))
  assert_equal(8 * 5 * 0.75, price([0, 1, 2, 3, 4]))
end

def test_several_discounts
  assert_equal(8 + (8 * 2 * 0.95), price([0, 0, 1]))
  assert_equal(2 * (8 * 2 * 0.95), price([0, 0, 1, 1]))
  assert_equal((8 * 4 * 0.8) + (8 * 2 * 0.95), price([0, 0, 1, 2, 2, 3]))
  assert_equal(8 + (8 * 5 * 0.75), price([0, 1, 1, 2, 3, 4]))
end

def test_edge_cases
  assert_equal(2 * (8 * 4 * 0.8), price([0, 0, 1, 1, 2, 2, 3, 4]))
  assert_equal(3 * (8 * 5 * 0.75) + 2 * (8 * 4 * 0.8), 
    price([0, 0, 0, 0, 0, 
           1, 1, 1, 1, 1, 
           2, 2, 2, 2, 
           3, 3, 3, 3, 3, 
           4, 4, 4, 4]))
end
51.20 이 아니라 51.60 아닌가요? 8*5*0.75 + 8*3*0.90 = 51.60 인데요..... - 취미로재미로, 2016/02/05 15:17 M D
1,2,3,4 1,2,3,5 이렇게 구매하면 51.2 - stardust, 2017/01/04 14:33 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

17개의 풀이가 있습니다. 1 / 2 Page

한계비용을 최소화하는 바구니에 책을 넣는 방법으로 만들었습니다.

import copy
def price(books):
    baskets = []
    for book in books:
        marginalcost = []
        for basket in baskets:
            temp_basket = copy.deepcopy(basket)
            temp_basket.add(book)
            marginalcost.append(calc(temp_basket) - calc(basket))
        try:
            minvalue = min([x for x in marginalcost if x])
            baskets[marginalcost.index(minvalue)].add(book)
        except:
            baskets.append({book})
    return sum([calc(x) for x in baskets])


def calc(bookset):
    DISCOUNT_RATE = (1, 1, 0.95, 0.9, 0.8, 0.75)
    if not bookset:
        return 0
    else:
        return len(bookset) * 8 * DISCOUNT_RATE[len(bookset)]
굉장히 효율적인 알고리즘인거 같습니다. 좀 자세한 설명 부탁드려도 될까요? - 길가의풀, 2014/12/29 16:05 M D
취미로 배우는 초보인데, 칭찬해주셔서 감사합니다. 1. 책 리스트를 받습니다.(books) 2. 최적의 경우를 계산할 수 있도록 바구니들의 리스트를 만듭니다.(baskets) 3. 책 리스트에서 책을 한권씩 꺼냅니다(book). 4. 이미 책 바구니가 있는 경우에는 책을 각 바구니에 시험삼아 넣어 보고, 각 바구니에 넣었을 때의 한계비용을 측정합니다. 각 바구니의 한계비용은 한계비용 리스트 내(marginalcost) 각각 저장합니다. 한계비용 = 한 권의 책을 추가로 넣었을 경우 늘어나는 비용 ex. {0, 1} 인 바구니에 2를 넣는 경우 한계비용은 8(책가격)*3(권수)*0.9(할인율) - 8*2*0.95(원래 바구니의 책값) 21.6-15.2 = 6.4 (바구니들은 set이기 때문에 바구니에 이미 있는 항목을 넣는 행동은 무효입니다. 따라서 marginalcost를 0으로 만듭니다.) 5. 0이 아닌 한계비용 중에서 최소값을 구합니다. 5.1. 한계비용이 가장 작은 바구니에 책을 넣습니다. 5.2. 각 바구니의 한계비용이 모두 0이거나 바구니가 한개도 없으면 바구니를 하나 만들고 그 안에 책을 넣습니다. 6. 각 책에 대해 3~5를 반복합니다. 7. 책을 바구니에 모두 잘 넣었으면 각 바구니의 책값을 모두 합산하여 가격을 알려줍니다. - 투플러스, 2014/12/30 18:44 M D
설명 감사합니다. set 을 이용해서 중복일 경우 무효처리하는 부분이 흥미롭네요 ^^, 거의 최적의 알고리즘인 것 같은데 이런 생각을 하신게 대단한거 같네요.. 전 재귀로 풀어보다가 느린 속도에 멘붕하고 포기하고 있었거든요. - 길가의풀, 2014/12/30 23:01 M D
알고리즘은 잘 설명해 주셨는데 제가 초보라.. 코드가 잘 읽어 지지가 않네요; 함수 콜 방법이 price([2,2,2,1,1]) 이렇게 하면 되는게 맞나요? 결과 값이 다르게 나와서요 - Starleaguer, 2015/03/22 13:23 M D
price([2,2,2,1,1]) 하면 [{2}] [{2}, {2}] [{2}, {2}, {2}] [{1, 2}, {2}, {2}] [{1, 2}, {1, 2}, {2}] 요렇게 돼서 38.4가 나오네요 - 투플러스, 2015/03/26 21:37 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

python 3.4.1 에서 만들어본 코드입니다.
기본적으로는 인자로 들어오는 책 리스트에서 가장 긴 (서로 다른) 책 묶음을 가려내서 계산하고,
그 묶음을 뺀 나머지 책 리스트에서 가장 긴 책 묶음을 가려내서 또 계산하는 걸 반복합니다.
하지만 책 할인율이 2권 5%, 3권 10%, 4권 20%, 5권 25% 으로,
3권에서 4권으로 넘어갈 때 할인율이 5% 가 아닌 10% 가 증가하기 때문에,
5권, 3권 조합보다는 4권, 4권 조합이 전체 가격을 낮추게 됩니다. 이 외의 경우에는 모두 그냥 가장 긴 (서로 다른) 책 묶음을 가려내서 계산하면 됩니다.

BOOK_PRICE = {1: 8 * 1,
              2: 8 * 0.95,
              3: 8 * 0.9,
              4: 8 * 0.8,
              5: 8 * 0.75}

def subtract_list_set(olist, oset):
    subtracted_list = [item if item not in oset else oset.remove(item) for item in olist]
    return([item for item in subtracted_list if item is not None])

def price(input_list):
    output_list = []
    while len(input_list) != 0:
        largest_pairs = set(input_list)
        output_list.append(len(largest_pairs))
        input_list = subtract_list_set(input_list, largest_pairs)
    if 5 in output_list and 3 in output_list:
        output_list.remove(5)
        output_list.remove(3)
        output_list.extend([4, 4])
    result = [item * BOOK_PRICE[item] for item in output_list]
    return(sum(result))

2015/01/05 22:38

Tim

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

3권 5권일때보다 4권 4권일때가 더 싸고 나머지의 경우엔 쌓일수록 싸기 때문에 일단 5권 묶음이 최대한으로 나오도록 한 다음 3권 5권 묶음을 4권4권으로 바꾸었습니다.

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int books[5]={1,1,2,2,2};
    int basket[5]={0,},t=0;
    int books_price[5]={300,256,216,152,80};
    sort(books,books+5);
    for(int i=0;i<5;i++)
    {
        basket[i]=books[i]-t;
        t=books[i];
    }
    if(basket[0]>basket[2])
    {
        basket[0]-=basket[2];
        basket[1]+=(basket[2]*2);
        basket[2]=0;
    }
    else
    {
        basket[2]-=basket[0];
        basket[1]+=(basket[0]*2);
        basket[0]=0;
    }
    int sum=0;
    for(int i=0;i<5;i++)
        sum+=books_price[i]*basket[i];
    printf("%lf\n",sum/10.0);

    return 0;
}

다른분들 풀이를 보니 초보자는 웁니다 ㅠㅠ

O(k)로 해결해서 잘풀었다고 생각하고 있었는데 ... 초보자는 울다니요ㅜ 낚였습니다...; 늦었지만 저도 같은 알고리즘을 생각해서 풀었네요~ - Starleaguer, 2015/03/23 01:56 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

일단 조건은 만족했는데 쪼개는 부분의 코드가 좀 지저분 하네요.

class Books < Array
  FULL_SET = [*0..4]
  def price
    if uniq?
      8 * size * (1.0 - discount_rate)
    else
      uniqs, others = split
      uniqs.price + others.price
    end
  end

  private
  def uniq?
    uniq.size == size
  end

  def split
    set_index = []
    uniqs = Books.new
    others = dup
    others.each_with_index do |book, index|
      if !uniqs.include?(book) && FULL_SET.include?(book)
        set_index.unshift index
        uniqs << book
      end
    end
    set_index.each { |i| others.delete_at(i) }
    if others.uniq.size == 3 && uniqs.size == 5
      i = (uniqs - others.uniq).first
      uniqs.delete i
      others << i
    end
    [uniqs, others]
  end

  def discount_rate
    case size
    when 2 then 0.05
    when 3 then 0.10
    when 4 then 0.20
    when 5 then 0.25
    else
      0
    end
  end
end

def price(books)
  Books.new(books).price
end
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
# 주어진 문제에서 모든 가격 책정의 경우를 구하기 위해 분할을 이용하였습니다. 예를 들어, 예시에 나오는 8권은 5+3, 5+2+2, 4+4, 4+2+2, 등등등 많은 분할의 수를 가집니다. 이걸 다 구하고 더해서 가장 작은 값을 출력하였습니다. 이 코드에 좋은 점은 100권 0권 2권 17권 0권 이런 식의 다양한 경우에 대해서도 신뢰할 수 있는 값을 구할 수 있다는 것입니다.(왜냐면 무식하게 다 구한거니깐...)

def bookdiscount():

    print "Choose the Harry Potter Edition.(input NUNMER as integer)"

    a = []
    for i in range(5):
        a.append(int(raw_input("%s'th edition : " % (i+1))))

    book = 0
    kind = 0

    for i in a:
        book = book + i
        if i>0: kind = kind +1

    pp = []
    pt = []
    ct = []

    for i in range(kind):
        k = kind - i
        for b in range((book/k)):
            pt = f(book-b*k, k)
            pt.extend([k]*b)
            pt.sort()
            pp.append(pt)

    for i in range(len(pp)):
        for j in pp[i+1:]:
            if pp[i] == j:
                pp.remove(j)

    for l in pp:
        ct.append(cost(l))

    ct.sort()
    set(ct)

    print "Possible Cost : "+str(list(set(ct)))     
    print "Minimum Cost is %s EUR." % ct[0]



def f(b, k):
    p = []

    while b > k:
        p.append(k)
        b = b-k
    p.append(b)

    return p


def cost(l):

    cos = 0

    for i in l:
        if i==1: cos = cos + 8
        elif i==2: cos = cos + 8*i*0.95
        elif i==3: cos = cos + 8*i*0.9
        elif i==4: cos = cos + 8*i*0.8
        elif i==5: cos = cos + 8*i*0.75

    return cos
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

내림차순으로 sort후에

앞에 값을 뒤의 값으로 빼준다.

5권,3권 < 4권,4권 예외처리한다.

값을 보여준다.

빅오로 O(k) 네요..

def main(book):
    book.sort(reverse=True)

    for i in range(4):
        if book[i]:
            book[i] -= book[i+1]

    nMin = min(book[4], book[2])

    if nMin:
        book[4] -= nMin
        book[2] -= nMin
        book[3] += nMin*2

    printPrice(book)

def printPrice(book):
    PRICES = [1, 0.95, 0.9, 0.8, 0.75]
    total = 0.0
    for i in range(5):
        total += book[i] * (i+1) * 8 * PRICES[i]
    print total

main([2,2,2,1,1])
main([2000,1000,500,10,1])
main([19023126192856123,8012389197123000,9000123000,5000123100,1000])
결과
51.2
26444.0
2.09874289363e+17
[Finished in 0.1s]
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
// SP_Herry.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"
#include<algorithm>
#include<vector>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    vector<int> vt;
    vt.push_back(2);    vt.push_back(3);    vt.push_back(2);    vt.push_back(1);    vt.push_back(1);
    sort(vt.begin(),vt.end());
    double dDiscountRate[5] = {0.25,0.20,0.10,0.05}; 
    int nBookPrice = 40;
    double  dPrice = 0;
    for(int iter = 0 ; iter< 5 ; iter++)
    {
        dPrice += vt[iter] * nBookPrice * ( 1.0 -  dDiscountRate[iter]);
        for(int i = iter+1 ; i < 5 ; i++)
        {
            vt[i] -= vt[iter];
        }
        nBookPrice-=8;
    }
    printf("total cost : %f EUR",dPrice);
    return 0;
}


※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
static void exce74()
    {
        int[] books = new int[5],basket;
        int chk = -1,total = 0,indx=0;
        double price = 0;
        Scanner scan = new Scanner(System.in);

        for (int i = 0; i < 5; i++)
        {
            System.out.printf("%d권 구입 수 : ", i + 1);
            books[i] = scan.nextInt();
            total += books[i];
        }

        basket = new int[total];

        while (chk != 0)
        {
            int cnt = 0;
            chk = 0;
            for (int i = 0; i < 5; i++)
            {
                if (books[i] > 0)
                {
                    cnt++;
                    chk++;
                    books[i]--;
                }
            }
            if(chk!=0)
            basket[indx++] = cnt;
        }

        for(int i=1;i<=total/5;i++)
        {
            if(basket[i] == 3)
            {
                basket[0]--;
                basket[i]++;
            }
        }

        for(int i=0;i<=total/5;i++)
        {
            switch(basket[i])
            {
                case 1:
                    price += 8;
                    break;
                case 2:
                    price += (8*2)*0.95;
                    break;
                case 3:
                    price += (8*3)*0.9;
                    break;
                case 4:
                    price += (8*4)*0.8;
                    break;
                case 5:
                    price += (8*5)*0.75;
                    break;
            }
        }

        System.out.println(price);
        scan.close();
    }

5,3 -> 4,4 로 바뀌는 경우 외외에는 한묶음이 많을수록 무조건 더 싸지므로 저 경우를 찾아서 바꿔주는식으로 구하였습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

다른 분들 답 보고 깨달았습니다. 4권과 3권 차이였군요!


a = [ 2000, 1000, 500, 10, 1 ]
b = [ 0, 0, 0, 0, 0 , 0 ]  
discount = [ 0, 0, 5, 10, 20, 25 ]  
sum = 0.0

while (True) :  
    cnt = 0
    for i in range(5) :
        if ( a[i] > 0 ) : cnt+=1 ; a[i] -= 1    
    if cnt == 0 : break
    b[cnt] += 1

if ( b[3] > b[5] ) :
    b[3] -= b[5] ; b[4] += 2 * b[5] ; b[5] = 0
else :
     b[4] += 2* b[3] ; b[5]-= b[3] ; b[3] = 0 

for i in range(6) :
    sum += b[i] * i * 8.0 * ( 100.0 - discount[i] ) / 100 

print sum  

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
l=list(map(int,input().split()))
l.sort()
l.reverse()
print(l)
m1=l[0]-l[1]
m2=l[1]-l[2]
l[2]
if l[3]+l[4]>=l[2]:
    m4=l[2]
    m5=l[3]+l[4]-l[2]
    m4=m4-m5
else:
    m4=l[3]+l[4]
    m5=0
m3=l[2]-m4-m5
print(m1,m2,m3,m4,m5)
price=m1*8+m2*15.2+m3*21.6+m4*25.6+m5*30
print(price)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 17
python x 10
cpp x 2
기 타 x 3
java x 1
ruby x 1