https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
< 📝 문제 >
김 프로는 수영장을 이용한다.
김 프로는 지출이 너무 많아 내년 1년 동안 각 달의 이용 계획을 수립하고 가장 적은 비용으로 수영장을 이용할 수 있는
방법을 찾고 있다.
수영장에서 판매하고 있는 이용권은 아래와 같이 4 종류이다.
① 1일 이용권 : 1일 이용이 가능하다.
② 1달 이용권 : 1달 동안 이용이 가능하다. 1달 이용권은 매달 1일부터 시작한다.
③ 3달 이용권 : 연속된 3달 동안 이용이 가능하다. 3달 이용권은 매달 1일부터 시작한다.
(11월, 12월에도 3달 이용권을 사용할 수 있다 / 다음 해의 이용권만을 구매할 수 있기 때문에 3달 이용권은 11월, 12월, 1윌 이나 12월, 1월, 2월 동안 사용하도록 구매할 수는 없다.)
④ 1년 이용권 : 1년 동안 이용이 가능하다. 1년 이용권은 매년 1월 1일부터 시작한다.
각 달의 이용 계획은 [Table 1]의 형태로 수립된다.
[Table 1]
1월 | 2월 | 3월 | 4월 | 5월 | 6월 | 7월 | 8월 | 9월 | 10월 | 11월 | 12월 | |
이용 계획 | 0일 | 0일 | 2일 | 9일 | 1일 | 5일 | 0일 | 0일 | 0일 | 0일 | 0일 | 0일 |
이용 계획에 나타나는 숫자는 해당 달에 수영장을 이용할 날의 수를 의미한다.
각 이용권의 요금과 각 달의 이용 계획이 입력으로 주어질 때,
가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 그 비용을 정답으로 출력하는 프로그램을 작성하라.
< ❓ 생각 >
1.
2.
< 💻 코드 >
1.
# n : n월, ssum : 비용
def DFS(n,ssum):
global ans
if n > 12:
if ans > ssum:
ans = ssum
return
# 1일
DFS(n+1, ssum + month[n]*day)
# 1달
DFS(n + 1, ssum + mon)
# 3달
DFS(n + 3, ssum + mon3)
# 1년
DFS(n + 12, ssum + year)
# 테스트 케이스 개수
T = int(input())
for tc in range(1,T+1):
# 이용권 가격들 (1일,1달,3달,1년)
day, mon, mon3, year = map(int,input().split())
# 12개월 이용 계획
month = [0]+list(map(int,input().split()))
ans = 1000000000000
DFS(1,0)
print(f'#{tc} {ans}')
2.
T = int(input())
for tc in range(1, T + 1):
day, mon, mon3, year = map(int, input().split())
month = [0]+list(map(int, input().split()))
D = [0]*13
for i in range(1, 13):
# 1일
mmin = D[i-1] + month[i]*day
# 1달
mmin = min(mmin, D[i-1] + mon)
# 3달
if i>=3:
mmin = min(mmin, D[i - 3] + mon3)
# 1년
if i>=12:
mmin = min(mmin, D[i - 12] + year)
D[i]=mmin
print(f'#{tc} {D[12]}')
< ❗ 느낀 점 >
이제 슬슬 DFS와 재귀에 대하여 깨우쳐 가는 느낌이다. 뿌듯
'TIL - 프로그래밍 > Python 알고리즘' 카테고리의 다른 글
[Python] baby-gin 재귀 (0) | 2022.03.27 |
---|---|
[SWEA] 2105. 디저트 카페 - Python (0) | 2022.03.25 |
[SWEA] 14141. 이진수 - Python (0) | 2022.03.23 |
[SWEA] 14142. 이진수2 - Python (0) | 2022.03.22 |
[SWEA] 1240. 단순 2진 암호코드 - Python (0) | 2022.03.21 |
댓글