wodud921   3년 전

# 상황

A주머니(3코인필요) -> [ 빨간색구슬, 주황색구슬 ]

B주머니(2코인필요) -> [ 노란색구슬, 초록색구슬 ]

C주머니(2코인필요) -> [ 파란색구슬 ]

D주머니(1코인필요) -> [ 남색구슬, 보라색구슬 ]

E주머니(1코인필요) -> [ ]

# 조건

1) 구슬은 한번에 하나만 뽑을 수 있다.

2) 구슬을 꺼낼때 마다 코인이 소비된다.

3) 각 경우의 수 마다 최대 9코인 까지 사용 가능하다.

4) 최소한 1개는 뽑아야 한다.

# 문제

구슬을 뽑을 수 있는 모든 경우의 수를 나열하라.

# 예시

## 1개를 뽑는 경우

1) (빨간색구슬) -> 3코인소비, 가능

2) (보라색구슬) -> 1코인소비, 가능

## 2개를 뽑는 경우

3) (빨간색구슬, 주황색구슬) -> 6코인소비, 가능

4) (빨간색구슬, 파란색구슬) -> 5코인소비, 가능

## 3개를 뽑는 경우

5) (빨간색구슬, 파랑색구슬, 남색구슬) -> 6코인소비, 가능

## 4개를 뽑는 경우

6) (빨간색구슬, 파랑색구슬, 남색구슬, 보라색구슬) -> 7코인소비, 가능

7) (빨간색구슬, 주황색구슬, 노란색구슬, 초록색구슬) -> 10코인소비, 불가능

Q) 파이썬으로 짜보려고 하는데 어떤 알고리즘으로 접근해야 할까요?

비슷한 문제가 있으면 어떤 것이 있는지 알려주실 수 있나요?

mastershim   3년 전

코인 제한이 9개고 경우의 수가 주머니 5개 밖에 없다면 저는 완전 탐색으로 풀 거 같네요.

itertools 모듈의 combinations를 사용해서 모든 조합을 다 해보면 금방 나올 거 같습니다.

댓글을 작성하려면 로그인해야 합니다.