후기 - 2번을 못풀었지만.. 기억더듬어보면서 풀어봄

#### 대충 아래처럼 풀었는데 풀이는 나중에 하겠음

 

( 문제 )

일단 입력으로 날짜와, [비용, 지속시간]이 주어집니다. ( 날짜는 중복될 수 있습니다 )
[비용] 을 지불하면 [지속시간]만큼 이용할 수 있습니다.

날짜 예시
["2022/05/02", "2022/05/01", "2022/05/07", "2022/05/05", "2022/05/08", "2022/05/13~2022/05/15", "2022/05/14~2022/05/17", "2022/05/01~2022/05/02", "2022/05/16"]
비용지속 시간 예시
[[3200, 4], [2300, 2], [1100, 1], [4200, 6]]

 

[코드]

from datetime import datetime, timedelta
import copy


def date_range(start, end):
    start = datetime.strptime(start, "%Y/%m/%d")
    end = datetime.strptime(end, "%Y/%m/%d")
    dates = [(start + timedelta(days=i)).strftime("%Y/%m/%d") for i in range((end-start).days+1)]
    return dates


# 출력
# ['2021-01-01', '2021-01-02', '2021-01-03', '2021-01-04', '2021-01-05', '2021-01-06', '2021-01-07', '2021-01-08', '2021-01-09']
dates = ["2022/05/02", "2022/05/01", "2022/05/07", "2022/05/05", "2022/05/08", "2022/05/13~2022/05/15", "2022/05/14~2022/05/17", "2022/05/01~2022/05/02", "2022/05/16"]
masks = [[3200, 4], [2300, 2], [1100, 1], [4200, 6]]
masks1 = [[100, 365], [3200, 4], [2300, 2], [1100, 1], [4200, 6]]
dates1 = ["2023/01/01~2023/01/02", "2021/12/31"]


def soltion(masks, dates):
    answer = 0
    dates.sort()
    dic = {}
    alldays = []
    dates.sort()
    print(dates)

    for date in dates:
        if "~" in date:
            st, end = date.split("~")

            days = date_range(st, end)
            alldays.extend(days)
        else:
            alldays.append(date)

    # print(alldays)
    setalldays = list(set(alldays))
    setalldays.sort()
    print(setalldays)
    tmp = copy.deepcopy(setalldays) ###

    masks.sort()
    terms = []
    # 마스크 최적화
    for ma in masks:
        money, term = ma
        terms.append(term)

    newmasks = []
    for ma in masks:
        money, term = ma
        newmasks.append([money, term])
        for t in terms:
            if t >= term:
                newmon = money * t

                if (t * term) > max(terms):
                    continue
                if [newmon, t * term] not in newmasks:
                    newmasks.append([newmon, t * term])

    # 최적화 이후 비용순으로 정렬
    newmasks.sort(key=lambda x: (x[0], -x[1]))
    length = len(setalldays)
    print(newmasks)
    dicma = {}
    for nm in newmasks:
        mon, ran = nm
        if ran not in dicma:
            dicma[ran] = mon
        else:
            if dicma[ran] > mon:
                dicma[ran] = mon
    print(dicma)
    # print(setalldays)
    ans1 = 0
    while True:
        if not setalldays:
            break

        canUseMask = newmasks[0][1]
        ans1 += newmasks[0][0]

        d = setalldays.pop(0)
        # datetime.datetime.strptime("21:00:00", "%H:%M:%S")
        enddate = datetime.strptime(d, "%Y/%m/%d") + timedelta(days=canUseMask)

        yed, non = str(enddate).split(" ")
        idx = 0

        for s in setalldays:
            if yed >= s:
                idx += 1
        setalldays = setalldays[idx:]

    prev = tmp[0]
    groups = []
    init = 1
    for idx in range(1, len(tmp)):
        cur = tmp[idx]
        target = datetime.strptime(prev, "%Y/%m/%d") + timedelta(days=1)
        use, notuse = str(target).split(" ")
        realuse = use.replace("-", "/")
        # print(realuse, cur)
        if realuse == cur:
            init += 1
            prev = cur
        else:
            groups.append(init)
            init = 1
            prev = cur
    groups.append(init)

    ans2 = 0
    for g in groups:
        if g in dicma:
            ans2 += dicma[g]
        else:
            for i in dicma:
                if i > g:
                    ans2 += dicma[i]
                    break

    answer = min(ans1, ans2)
    return answer


sol = soltion(masks, dates)
print(sol)

 

[코드]

mask2 같은 경우 고려

 

dates = ["2022/05/02", "2022/05/01", "2022/05/07", "2022/05/05", "2022/05/08", "2022/05/13~2022/05/15", "2022/05/14~2022/05/17", "2022/05/01~2022/05/02", "2022/05/16"]
masks = [[3200, 4], [2300, 2], [1100, 1], [4200, 6]]
masks1 = [[100, 365], [3200, 4], [2300, 2], [1100, 1], [4200, 6]]
masks2 = [[5000, 10], [3200, 4], [2300, 2], [1100, 1], [4200, 6]]
dates1 = ["2023/01/01~2023/01/02", "2021/12/31"]


def soltion(masks, dates):
    answer = 0
    dates.sort()
    dic = {}
    alldays = []
    dates.sort()
    print(dates)

    for date in dates:
        if "~" in date:
            st, end = date.split("~")

            days = date_range(st, end)
            alldays.extend(days)
        else:
            alldays.append(date)

    # print(alldays)
    setalldays = list(set(alldays))
    setalldays.sort()
    print(setalldays)
    tmp = copy.deepcopy(setalldays) ###

    masks.sort()
    terms = []
    # 마스크 최적화
    for ma in masks:
        money, term = ma
        terms.append(term)

    newmasks = []
    for ma in masks:
        money, term = ma
        newmasks.append([money, term])
        for t in terms:
            if t >= term:
                newmon = money * t

                if (t * term) > max(terms):
                    continue
                if [newmon, t * term] not in newmasks:
                    newmasks.append([newmon, t * term])

    # 최적화 이후 비용순으로 정렬
    newmasks.sort(key=lambda x: (x[0], -x[1]))
    length = len(setalldays)
    print(newmasks)
    dicma = {}
    for nm in newmasks:
        mon, ran = nm
        if ran not in dicma:
            dicma[ran] = mon
        else:
            if dicma[ran] > mon:
                dicma[ran] = mon
    print(dicma)

    kwonmasks = []
    for di in dicma:
        kwonmasks.append([dicma[di], di])
    kwonmasks.sort(key=lambda x:(x[0]//x[1]))
    print(kwonmasks)
    print(setalldays)
    ans1 = 0
    idx = 0
    while True:
        if not setalldays:
            break

        length = len(setalldays)
        lastt = datetime.strptime(setalldays[length - 1], "%Y/%m/%d")
        fistt = datetime.strptime(setalldays[0], "%Y/%m/%d")

        timelen = lastt - fistt
        wantdays = str(timelen).split(" ")
        print("wandays", wantdays[0], end=" ")

        index = 0
        while True:
            if int(wantdays[0]) >= kwonmasks[index][1]:
                canUseMask = kwonmasks[index][1]
                ans1 += kwonmasks[index][0]
                break
            else:
                index += 1

        d = setalldays.pop(0)
        # datetime.datetime.strptime("21:00:00", "%H:%M:%S")
        enddate = datetime.strptime(d, "%Y/%m/%d") + timedelta(days=canUseMask)
        yed, non = str(enddate).split(" ")
        # "2022-05-11"
        # '2022/05/01'
        yed = yed.replace("-", "/")
        print(yed)
        for s in setalldays:
            if yed >= s:
                idx += 1
        setalldays = setalldays[idx:]

    prev = tmp[0]
    groups = []
    init = 1
    for idx in range(1, len(tmp)):
        cur = tmp[idx]
        target = datetime.strptime(prev, "%Y/%m/%d") + timedelta(days=1)
        use, notuse = str(target).split(" ")
        realuse = use.replace("-", "/")
        # print(realuse, cur)
        if realuse == cur:
            init += 1
            prev = cur
        else:
            groups.append(init)
            init = 1
            prev = cur
    groups.append(init)
    print(groups)

    ans2 = 0
    for g in groups:
        if g in dicma:
            ans2 += dicma[g]
        else:
            for i in dicma:
                if i > g:
                    ans2 += dicma[i]
                    break

    answer = min(ans1, ans2)
    return answer