1952. [모의 SW 역량테스트] 수영장

13222 단어 SWEASWEA

문제


문제링크

코드

tc 47/50 코드
사유 : 3개월 1개월보다 1개월 3개월이 이득일 경우를 고려하지 못함

T = int(input())
for tc in range(1, T+1):
    d, m, m3, y = map(int, input().split())
    p = list(map(int, input().split()))
    tot = [0]*12
    res = 0
    for i in range(12):
        if p[i]*d > m:
            tot[i] = m
        else:
            tot[i] = p[i]*d
    res = sum(tot)
    for j in range(10):
        if sum(tot[j:j+3]) > m3 and not 1 in tot[j:j+3]:
            tot[j], tot[j+1], tot[j+2] = 1, 1, 1
    if 1 in tot:
        res = (tot.count(1)//3)*m3+sum(tot)-tot.count(1)
    else:
        res = sum(tot)
    if res > y: res = y
    print('#{} {}'.format(tc, res))

통과코드

T = int(input())
for tc in range(1, T+1):
    d, m, m3, y = map(int, input().split())
    p = [0]+list(map(int, input().split()))
    dp = [0]*13
    dp[1] = min(m, p[1]*d)
    dp[2] = dp[1] + min(m, p[2]*d)
    for i in range(3, 13):
        dp[i] = min(dp[i-3]+m3, dp[i-1]+p[i]*d, dp[i-1]+m)
    print('#{} {}'.format(tc, min(dp[-1], y)))

풀이

통과코드만 풀이하자면 DP로 (아직 이해 완벽히는 못함) 각 월의 가장 최소금액을 저장해나가는 것임
dp[1], dp[2]는 앞에 3개월이 필요하지 않고 일일 계산이나 한달 계산밖에 없기 때문에 해주는 것이고 나머지는 3개월금액까지 고려해야 하기때문에 반복문을 돌렸다.
처음부터 반복문을 돌려서 if조건문으로 i-3이 유효할때 어쩌고 해서 해줘도 될거 같은데 그러면 복잡해서 이렇게 하는 것 같음

좋은 웹페이지 즐겨찾기