# 상황
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) 파이썬으로 짜보려고 하는데 어떤 알고리즘으로 접근해야 할까요?
비슷한 문제가 있으면 어떤 것이 있는지 알려주실 수 있나요?
코인 제한이 9개고 경우의 수가 주머니 5개 밖에 없다면 저는 완전 탐색으로 풀 거 같네요.
itertools 모듈의 combinations를 사용해서 모든 조합을 다 해보면 금방 나올 거 같습니다.
댓글을 작성하려면 로그인해야 합니다.
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) 파이썬으로 짜보려고 하는데 어떤 알고리즘으로 접근해야 할까요?
비슷한 문제가 있으면 어떤 것이 있는지 알려주실 수 있나요?