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
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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

재귀를 통해 모든 경우의 수 중 최소 값을 구합니다.

제약조건으로 책을 내림차순으로 정렬했다고 가정....

내림차순 정렬까지 추가하기는 손이 가다보니 생략ㅠ,.ㅠ

#include <stdio.h>
#include <stdlib.h>

bool verdict(int book[5]);
void function(int book[5], double sum);

int price = 8;
double min = 1000;
void main() {
    int book[5] = {2,2,2,1,1};
    double value = 0;
    function(book, 0);
    printf("%f", min);

}
void function(int book[5], double sum) {
    double ex_sum = sum;
    double price = 1;
    int copy[5];
    for(int i=0;i<5;i++) 
        copy[i] = book[i];

    for(int i=1;i<6;i++) {
        sum = ex_sum;
        int count = 0;
        for(int j=0;j<5;j++) {
            if(copy[j] > 0)
                count++;
            book[j] = copy[j];
        }

        if(count == 0) {
            if(sum < min)
                min = sum;
            break;
        }
        if(i==1 && count >= 1) {
            price = 1*8;
            int j=0;
            int c=0;
            while(1) {
                if(book[j] > 0) {
                    book[j]--;
                    c++;
                }
                if(c==i) break;
                j++;
            }
        }
        else if(i==2 && count >= 2) {
            price = 2*8*0.95;
            int j=0;
            int c=0;
            while(1) {
                if(book[j] > 0) {
                    book[j]--;
                    c++;
                }
                if(c==i) break;
                j++;
            }
        }
        else if(i==3 && count >= 3) {
            price = 3*8*0.90;
            int j=0;
            int c=0;
            while(1) {
                if(book[j] > 0) {
                    book[j]--;
                    c++;
                }
                if(c==i) break;
                j++;
            }
        }
        else if(i==4 && count >= 4) {
            price = 4*8*0.80;
            int j=0;
            int c=0;
            while(1) {
                if(book[j] > 0) {
                    book[j]--;
                    c++;
                }
                if(c==i) break;
                j++;
            }
        }
        else if(i==5 && count >= 5) {
            price = 5*8*0.75;
            int j=0;
            int c=0;
            while(1) {
                if(book[j] > 0) {
                    book[j]--;
                    c++;
                }
                if(c==i) break;
                j++;
            }
        }
        else
            break;
        sum = sum + price;
        function(book, sum);
    }
}

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

Ruby

discnt = ->pack { [0, 1, 0.95, 0.9, 0.8, 0.75][pack.size] * 8 * pack.size }
price = ->cart { cart.empty? ? 0 : cart.map(&discnt).reduce(:+) }
min_cart = ->cart,book do
  make_cases = ->i,t=cart.dup { t[i]+=[book]; t if t.all? {|_|_.size==_.uniq.size} }
  ((0...cart.size).map(&make_cases).compact << cart+[[book]]).min_by &price
end
min_price = ->books,cart=[],book=books.shift do
  book ? min_price[books, min_cart[cart,book]] : price[cart]
end

Test

no_discnt_cases = [[], [0], [0,0]] 
simple_cases    = [[0,1], [0,2,4]]
several_cases   = [[0,0,1], [0,0,1,1], [0,0,1,2,2,3]]
edge_cases      = [ [0,0,1,1,2,2,3,4],  [0, 0, 0, 0, 0,
                                         1, 1, 1, 1, 1,
                                         2, 2, 2, 2,
                                         3, 3, 3, 3, 3,
                                         4, 4, 4, 4] ]

expect( no_discnt_cases.map(&min_price) ).to eq [8*0, 8*1, 8*2]
expect( simple_cases.map(&min_price) ).to  eq [(8 * 2 * 0.95), (8 * 3 * 0.9)]
expect( several_cases.map(&min_price) ).to eq [(8 * 2 * 0.95) + (8 * 1 * 1.0), 
                                               (8 * 2 * 0.95) * 2,
                                               (8 * 2 * 0.95) + (8 * 4 * 0.8)]
expect( edge_cases.map(&min_price) ).to eq [(8 * 4 * 0.8) * 2, 
                                            (8 * 5 * 0.75) * 3 + 
                                            (8 * 4 * 0.8 ) * 2 ]

Output

p min_price[ [0,0,1,1,2,2,3,4] ] #=> 51.2
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

리스트의 리스트 형식으로 카트를 구성하고, 책을 하나씩 넣으면서 (단일 카트 내에는 중복된 책이 들어가지 않도록) 매번 책이 추가될 때마다 최소값이 되는 카트 구성을 찾고, 이 때의 최소값과 카트 구성을 리턴받게 됩니다. 이 과정을 매 책을 추가해가면서 반복합니다.

대신 이 과정은 책들이 정렬되어 있을 때만 올바르게 동작합니다. 따라서 입력받은 책 목록을 정렬한 후에 시행합니다.

def do(xs):
    def compute_price(carts):
        def compute_books(cart):
            discount = (0, 1, 0.95, 0.9, 0.8, 0.75)
            return len(cart) * 8 * discount[len(cart)]
        return sum([compute_books(cart) for cart in carts])


    def find_min_sum(carts, book):
        result = compute_price(carts) + 8
        result_cart = carts + [[book]]
        for i, cart in enumerate(carts):
            if book not in cart:
                _temp_cart = carts[:i] + [cart + [book]] + carts[i+1:]
                _result = compute_price(_temp_cart)
                if _result < result:
                    result = _result
                    result_cart = _temp_cart
        return result, result_cart


    carts = []
    for book in sorted(xs):
        m, carts = find_min_sum(carts, book)
    print(m, carts)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

c 코드로 입력했어요. 51.20 나옵니다. 처음에는 잘못코딩해서 51.60 나왔었어요.

#include <stdio.h>

int main(void)
{
    int aa = 0, bb = 0, cc = 0, dd = 0, ee = 0, ff = 0, gg = 0, hh = 0, ii = 0, e = 0, a = 0, b = 0, f = 0,  arr[10000], arr1[10000], arr4[10000];
    double g = 0.0;

    for(a = 0; a < 5; a++)
    {
        scanf("%d", &arr[a]);
    }
    for(a = 0; a < 5; a++)
    {
        b = b + arr[a];
        arr1[a] = arr[a];
    }
    g = b*8;
    a = 0;
    while(1)
    {
        if(arr1[a] >= 1)
        {
            arr4[bb] = 1;
            bb++;
            aa++;
        }
        else if(arr1[a]==0)
        {
            arr4[bb] = 0;
            aa++;
            bb++;
        }
        else if(arr1[a] < 0)
        {
            arr4[bb] = 0;
            aa++;
            bb++;
        }

        arr1[a] = arr1[a] - 1;
        a++;
        if(a==5)
        {
            a = 0;
            for(cc = bb - 5; cc < bb; cc++)
            {
                dd = dd + arr4[cc];
            }
            if(dd==0)
                break;
            dd = 0;
        }
    }
    for(a = 0; a < bb; a++)
    {
        if(arr4[a]!=0)
        {
            f = f + arr4[a];
        }
        if(a%5==4)
        {
            e = 5 - f;

            if(e==0)
            {
                g = g - 8*5*0.25;
            }
            else if(e==1)
            {
                g = g - 8*4*0.2;
            }
            else if(e==2)
            {
                g = g - 8*3*0.1;
            }
            else if(e==3)
            {
                g = g - 8*2*0.05;
            }
            else if(e==4)
            {
                g = g;
            }
            if(f==3)
            {
                hh++;
            }
            else if(f==5)
            {
                ii++;
            }
            ee++;
            f = 0;
            e = 0;
        }
    }
    if(hh > ii)
    {
        g = g + 8*5*0.25*ii;
        g = g + 8*3*0.1*hh;
        g = g - 2*8*4*0.2*ii;
    }
    else if(hh <= ii)
    {
        g = g + 8*5*0.25*ii;
        g = g + 8*3*0.1*hh;
        g = g - 2*8*4*0.2*hh;
    }
    printf("%f\n", (double) g);
    return 0;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
booklist = (raw_input("input the number of books to be bought, each divided by a space only:").split(" ")
result = 0
for i in range(len(booklist)):
    booklist[i]=eval(booklist[i])
while booklist[0]+booklist[1]+booklist[2]+booklist[3]+booklist[4] > 0:
    if booklist.count(0) == 0:
        for k in range(len(booklist)):
            booklist[k]-=1
                result += 8*5*0.75

    if booklist.count(0) == 1:
        for k in range(len(booklist)):
            if booklist[k] != 0:
                booklist[k] -= 1
        result += 8*4*0.80

    if booklist.count(0) == 2:
        for k in range(len(booklist)):
            if booklist[k] != 0:
                booklist[k]-=1
        result += 8*3*0.90

    if booklist.count(0) == 3:
        for k in range(len(booklist)):
            if booklist[k] != 0:
                booklist[k]-=1
        result += 8*2*0.95

    if booklist.count(0) == 4:
        for k in range(len(booklist)):
            if booklist[k] != 0:
                booklist[k]-=1
        result += 8

print result     

하이고..... IDE 하나가 고장이 나서 다른 걸로 하는데 복붙하면 들여쓰기한 게 다 망가진다는 걸 배웠습니다ㅠㅠ 그거 고치느라 한참 걸렸네요 분명 제대로 했는데 계속 에러 나고..... 그래서 복사해서 메모장에 붙여보니까 어떤 건 탭 되어있고 어떤 건 스페이스 되어있고..... 휴..... 그리고 문제에 51.20 이라고 되어있는데, 51.60 아닌가요?ㅠㅠ 그건 문제에 댓글 달았으니 봐주세요..... 그리고 질문 있습니다! 저 북리스트는 장바구니고, 각 원소는 각 시리즈의 구매 수입니다. 결국 장바구니에 하나라도 남은 시리즈가 몇 시리즈 되는지를 조건문으로 나누어서 푼 건데요, 질문은요, 보시면 아시다시피 조건문이 if 하고 if 하고 또 if 하고 이런 식입니다. if 하고 elif 하고 그랬더니 문법 오류라고 뜨더라구요ㅠㅠ 그건 왜 그런거죠? 아시는 분 제발 댓글 달아주세요ㅠㅠ 그리 잘 쓴 코드는 아니지만 그래도 푸는 건 수월했는데 웬 IDE 가 고장나고 옮기는데 형식이 다 깨지고 해서 짜증 이빠이 났네요..... 휴 그래도 첫 레벨4 문제인데 풀게 되어서 기쁩니당 호호 즐코딩!!!!!

아 질문 하나 더 있는데요, for i in booklist: i =+ 1 print booklist 하면 += 1 이 반영이 안되는데요, for i in range(len(booklist)): booklist[i] += 1 print booklist 하면 +=1이 반영이 되네요. 왜 그런거죠? - 취미로재미로, 2016/02/05 15:30 M D
다음과 같은 코드를 생각해봅시다. x = [1] for i in x i =+ 1 이 코드는 다음과 똑 같습니다. x=[1] i=1 i+=1 이렇게 하면 x의 내용이 절대 바뀔 리가 없죠. 일단 이것으로 위의 질문에 대한 답은 되었구요. 한가지 더 말씀드리자면, 좀 다른 경우가 생기는데 이것도 한번 생각해보세요. x=[[1]] for i in x: i[0] += 1 이렇게 하면 x의 내용이 바뀝니다.이것은 파이썬 자료형이 2가지가 있기 때문인데요, 바뀌지 않는 값(숫자, 문자열, 튜플)과 바뀌는 값(바뀌는 3가지를 제외한 모든것)이 할당문("="를 사용하는 문장)에서 일어나는 일이 다르기 때문입니다. 설명이 너무 길어지긴 합니다만, a=1 b=a b=2 a=? 그리고, a=[1] b=a b[0]=2 a=? 이렇게 하면 a의 값은 변할까요? 변하지 않을까요? 직접 테스트해보세요. 파이썬에서 아주 중요하고 꼭 이해하고 넘어가야 할 문제라서, 관련사항을 꼭 찾아보세요. 이거 모르면 프로그래밍 못해요. 디버깅 절대 못합니다. ㅎ - 상파, 2016/02/07 22:46 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

무식무식하게 큐 돌려서 풀었습니다.

copies = map(int, raw_input().split())
q=[[0]+copies]
res=[]
while q:
    tmp = q.pop(0)
    money = tmp[0]
    books = tmp[1:]
    books.sort(reverse=True)
    for n, price in [(1,8.0),(2,15.2),(3,21.6),(4,25.6),(5,30.0)]:
        books_copy = books[:]
        money_copy = money
        if len(books_copy) >= n:
            for i in range(n):
                books_copy[i] -= 1
            while 0 in books_copy : books_copy.remove(0)
            money_copy += price
            if not books_copy : res.append(money_copy)
            elif not [money_copy]+books_copy in q:
                q.append([money_copy]+books_copy)
print min(res)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
  • python으로 작성하였습니다. 큰묶음 우선으로 묶이도록 계산하되, 5권1묶음+3권2묶음 대신 4권 2묶음이 되도록 예외처리 하였습니다.(작은 묶음이 우선 계산되는 경우는 이경우 밖에 없는것 같네요)
salePrices=[8.0,8.0*0.95,8.0*0.9,8.0*0.8,8.0*0.75]

def getBookPrice(books):
    price=0
    cart=[0,0,0,0,0]

    while(True):
        cnt=0

        if(books.count(2)==3 and books.count(1)==2): #5*1,3*2 대신 4*2가 되도록
            cart[3]+=2;books=[0,0,0,0,0]
            break;

        for idx,book in enumerate(books):
            if book!=0:
                books[idx]=book-1
                cnt+=1

        if cnt!=0:
            cart[cnt-1]+=1
        else:
            break


    for idx,cnt in enumerate(cart):
        price+=cnt*(idx+1)*salePrices[idx] 

    return price

# test case
books=[2,2,2,1,1]
books1=[2,2,2,3,4]
books2=[4,4,4,2,2]

print getBookPrice(books)
print getBookPrice(books1)
print getBookPrice(books2)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def book_price(book, n, price_table):
    price = 0
    while True:
        if n > 5-book.count(0):
            n = 5-book.count(0)
            if n == 0:
                break
        price += n * 8 * price_table[n]
        for i in range(n):
            book[i] -= 1
        book.sort(reverse=True)
    return price


if __name__ == '__main__':
    discount = {2:0.95, 3:0.9, 4:0.8, 5:0.75}

    num_book = [2, 2, 2, 1, 1]
    num_book.sort(reverse=True)

    n_max = 5-num_book.count(0)
    price_list = [book_price(num_book[:],n,discount) for n in range(2,n_max+1)]

    print('Minimum price is %.2f EUR' % min(price_list))
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
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)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

다른 분들 답 보고 깨달았습니다. 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  

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

풀이 작성

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

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


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